Elements in the lattice $A_n$

Elements in the lattice

$A_n$

asked 9 years ago

emiliocba

141 ●6 ●11 ●20

updated 9 years ago

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)$ .

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

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

Francis Clarke ( 9 years ago )

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

emiliocba ( 9 years ago )

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

add a comment

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Elements in the lattice AnA_n savecancel

Comments

1 Answer

Comments