ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 24 Jun 2017 01:21:23 +0200Elements in the lattice $A_n$https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/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)$.
Tue, 19 May 2015 12:57:50 +0200https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/Comment by Luca for <p>Sorry in advance if this is not the right place to ask this simple question. </p>
<p>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$.</p>
<p>For example, if $n=1$ then $(k,-k)$ and $(-k,k)$ are all the elements in $A_1$ with norm equal to $k$.</p>
<p>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)$. </p>
https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/?comment=26877#post-id-26877I 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)`.Tue, 19 May 2015 14:23:21 +0200https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/?comment=26877#post-id-26877Comment by Francis Clarke for <p>Sorry in advance if this is not the right place to ask this simple question. </p>
<p>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$.</p>
<p>For example, if $n=1$ then $(k,-k)$ and $(-k,k)$ are all the elements in $A_1$ with norm equal to $k$.</p>
<p>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)$. </p>
https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/?comment=26893#post-id-26893Perhaps `Compositions(k, length=n+1)` would be closer to what you want.Wed, 20 May 2015 11:20:52 +0200https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/?comment=26893#post-id-26893Comment by emiliocba for <p>Sorry in advance if this is not the right place to ask this simple question. </p>
<p>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$.</p>
<p>For example, if $n=1$ then $(k,-k)$ and $(-k,k)$ are all the elements in $A_1$ with norm equal to $k$.</p>
<p>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)$. </p>
https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/?comment=26894#post-id-26894None of them works since the vectors may have zero and negative coordinates.Wed, 20 May 2015 12:47:05 +0200https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/?comment=26894#post-id-26894Comment by Luca for <p>Sorry in advance if this is not the right place to ask this simple question. </p>
<p>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$.</p>
<p>For example, if $n=1$ then $(k,-k)$ and $(-k,k)$ are all the elements in $A_1$ with norm equal to $k$.</p>
<p>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)$. </p>
https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/?comment=26901#post-id-26901Sorry, 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`.Wed, 20 May 2015 20:49:41 +0200https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/?comment=26901#post-id-26901Answer by Marcel for <p>Sorry in advance if this is not the right place to ask this simple question. </p>
<p>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$.</p>
<p>For example, if $n=1$ then $(k,-k)$ and $(-k,k)$ are all the elements in $A_1$ with norm equal to $k$.</p>
<p>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)$. </p>
https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/?answer=38051#post-id-38051I would suggest something like this
<pre>
k=2
Q=QuadraticForm(ZZ,2,[1,-1,1]);Q
m=Q.short_vector_list_up_to_length(k^2+1)
m[k^2]
</pre>
which is $A_2$ for some $k$ which gives the result in the basis $e_1=(1,-1,0), e_2=(0,1,-1)$.Thu, 22 Jun 2017 05:16:10 +0200https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/?answer=38051#post-id-38051Comment by Marcel for <p>I would suggest something like this</p>
<pre>k=2
Q=QuadraticForm(ZZ,2,[1,-1,1]);Q
m=Q.short_vector_list_up_to_length(k^2+1)
m[k^2]
</pre>
<p>which is $A_2$ for some $k$ which gives the result in the basis $e_1=(1,-1,0), e_2=(0,1,-1)$.</p>
https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/?comment=38074#post-id-38074Sorry this uses the wrong norm. Actually the norm of the OP is not a norm.Sat, 24 Jun 2017 01:21:23 +0200https://ask.sagemath.org/question/26873/elements-in-the-lattice-a_n/?comment=38074#post-id-38074