Ask Your Question
0

Elements in the lattice $A_n$

asked 2015-05-19 12:57:50 +0100

emiliocba gravatar image

updated 2015-05-20 12:53:31 +0100

Sorry in advance if this is not the right place to ask this simple question.

As it is usual, $A_n ={ (a_1,\dots,a_{n+1}) \in\mathbb Z^{n+1}:a_1+\dots+a_{n+1}=0}$. Now we define the norm $$ \|(a_1,\dots,a_{n+1})\|:= \sum_{i:a_i>0} a_i. $$ I would like an algorithm with input $(n,k)$, that returns all elements in $A_n$ with norm equal to $k$.

For example, if $n=1$ then $(k,-k)$ and $(-k,k)$ are all the elements in $A_1$ with norm equal to $k$.

For $n=2$ and $k=2$, we have $(2,0,-2), (2,-1,-1), (2,-2,0), (1,1,-2), (1,-2,1), (0,2,-2), (0,-2,2), (-1,2,-1), (-1,-1,2), (-2,2,0), (-2,0,2)$.

edit retag flag offensive close merge delete

Comments

I think you are looking for the integer partitions of k of length n+1. Have a look at the iterator Partitions(k,length=n+1).

Luca gravatar imageLuca ( 2015-05-19 14:23:21 +0100 )edit

Perhaps Compositions(k, length=n+1) would be closer to what you want.

Francis Clarke gravatar imageFrancis Clarke ( 2015-05-20 11:20:52 +0100 )edit

None of them works since the vectors may have zero and negative coordinates.

emiliocba gravatar imageemiliocba ( 2015-05-20 12:47:05 +0100 )edit
1

Sorry, misread your question. Here's some facts

  • The positive entries in your vector form a composition of k of length a ≤ n.
  • The absolute values of the negative entries form a composition of k of length b ≤ n + 1 - a.
  • The rest are zero entries.

So, a sketch of algorithm to generate one such vector would be :

  • Form all compositions of k of length at most n.
  • Choose a and b so that a+b ≤ n+1.
  • Choose the positions for the a positive coefficients, fill with a composition of length a.
  • Chose the positions for the b negative cofficients, fill with a composition of length b.
  • Fill the rest with zeros.

To iterate over all such vectors, you can use Sage's Compositions and Permutations.

Luca gravatar imageLuca ( 2015-05-20 20:49:41 +0100 )edit

1 Answer

Sort by » oldest newest most voted
0

answered 2017-06-22 05:20:13 +0100

Marcel gravatar image

I would suggest something like this

k=2
Q=QuadraticForm(ZZ,2,[1,-1,1]);Q
m=Q.short_vector_list_up_to_length(k^2+1)
m[k^2]

which is $A_2$ for some $k$ which gives the result in the basis $e_1=(1,-1,0), e_2=(0,1,-1)$.

edit flag offensive delete link more

Comments

Sorry this uses the wrong norm. Actually the norm of the OP is not a norm.

Marcel gravatar imageMarcel ( 2017-06-24 01:21:23 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2015-05-19 12:57:50 +0100

Seen: 649 times

Last updated: Jun 22 '17