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.Mon, 02 Mar 2020 16:08:29 +0100Iterate over multivariate polynomials over finite fieldshttps://ask.sagemath.org/question/50136/iterate-over-multivariate-polynomials-over-finite-fields/Say we have a finite field, e.g. $F_4$, and consider the $n$-ary polynomials $R=F_4[x_1,\dots,x_n]$ over this field.
I want to iterate over all these polynomials in $R$. Since the polynomials are over a finite field there are only finitely many different polynomials (considered as functions $F_4^n \to F_4$). How can I do this?
For $n=1$ I could do
R.<x> = PolynomialRing(GF(4))
S.<a> = R.quo(sage.rings.ideal.FieldIdeal(R))
S.is_finite()
Then I could iterate over $S$ and simply lift all the elements from $S$ back to $R$, i.e. s.lift(). The same thing however does not work for several polynomials:
R.<x,y> = PolynomialRing(GF(4))
S.<a,b> = R.quo(sage.rings.ideal.FieldIdeal(R))
S.is_finite()
yields the error
> AttributeError: 'super' object has no attribute 'is_finite'
As an alternative I could manually generate all multivariate polynomials with exponents less than the order of the field. However, this seems quite tedious and like a very "un-sage"/not algebraic way.Mon, 02 Mar 2020 15:27:09 +0100https://ask.sagemath.org/question/50136/iterate-over-multivariate-polynomials-over-finite-fields/Answer by rburing for <p>Say we have a finite field, e.g. $F_4$, and consider the $n$-ary polynomials $R=F_4[x_1,\dots,x_n]$ over this field.
I want to iterate over all these polynomials in $R$. Since the polynomials are over a finite field there are only finitely many different polynomials (considered as functions $F_4^n \to F_4$). How can I do this?
For $n=1$ I could do</p>
<pre><code>R.<x> = PolynomialRing(GF(4))
S.<a> = R.quo(sage.rings.ideal.FieldIdeal(R))
S.is_finite()
</code></pre>
<p>Then I could iterate over $S$ and simply lift all the elements from $S$ back to $R$, i.e. s.lift(). The same thing however does not work for several polynomials:</p>
<pre><code>R.<x,y> = PolynomialRing(GF(4))
S.<a,b> = R.quo(sage.rings.ideal.FieldIdeal(R))
S.is_finite()
</code></pre>
<p>yields the error</p>
<blockquote>
<p>AttributeError: 'super' object has no attribute 'is_finite'</p>
</blockquote>
<p>As an alternative I could manually generate all multivariate polynomials with exponents less than the order of the field. However, this seems quite tedious and like a very "un-sage"/not algebraic way.</p>
https://ask.sagemath.org/question/50136/iterate-over-multivariate-polynomials-over-finite-fields/?answer=50137#post-id-50137A vector space basis for $R/I$ is also called a *normal basis* for $I$. You can obtain it as follows:
sage: R.<x,y> = PolynomialRing(GF(4))
sage: NB = sage.rings.ideal.FieldIdeal(R).normal_basis(); NB
[x^3*y^3, x^2*y^3, x*y^3, y^3, x^3*y^2, x^2*y^2, x*y^2, y^2, x^3*y, x^2*y, x*y, y, x^3, x^2, x, 1]
Then you want to give these monomials all possible coefficients:
sage: from itertools import product
sage: [sum(c*m for (c,m) in zip(C,NB)) for C in product(R.base_ring(), repeat=len(NB))]
The output consists of $4^{16} = 4294967296$ polynomials.Mon, 02 Mar 2020 16:08:29 +0100https://ask.sagemath.org/question/50136/iterate-over-multivariate-polynomials-over-finite-fields/?answer=50137#post-id-50137