Loading [MathJax]/jax/output/HTML-CSS/jax.js

First time here? Check out the FAQ!

Ask Your Question
0

Elements in the lattice An

asked 10 years ago

emiliocba gravatar image

updated 10 years ago

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

As it is usual, An=(a1,,an+1)Zn+1:a1++an+1=0. Now we define the norm (a1,,an+1):=i:ai>0ai. I would like an algorithm with input (n,k), that returns all elements in An with norm equal to k.

For example, if n=1 then (k,k) and (k,k) are all the elements in A1 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).

Preview: (hide)

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 ( 10 years ago )

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

Francis Clarke gravatar imageFrancis Clarke ( 10 years ago )

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

emiliocba gravatar imageemiliocba ( 10 years ago )
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 ( 10 years ago )

1 Answer

Sort by » oldest newest most voted
0

answered 8 years ago

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 A2 for some k which gives the result in the basis e1=(1,1,0),e2=(0,1,1).

Preview: (hide)
link

Comments

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

Marcel gravatar imageMarcel ( 8 years ago )

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: 10 years ago

Seen: 741 times

Last updated: Jun 22 '17