I want to define polynomials with coefficients given in some range.

Namely, let $p$ be a prime number and $n$ be a positive integer. For all positive integer $k\leq n$ I want to generate all polynomials of degree $k$ with integer coefficients


such that $a[k]=1$, $a[0]\neq0$ and $0\leq a[i]\leq p-1$ for $1\leq i\leq k-1$.

How can I do this?

  • 2
    $\begingroup$ …but no other restrictions on $a[0]$? There are a lot of integers $\ne 0$… $\endgroup$
    – J. M.'s torpor
    Jun 24 '15 at 19:55

I post this for illustration. As @Xilin has commented there is a combinatorial explosion from early. If some small number cases are desired and assuming $1\le a_0\le p-1$ and all polynomials of degree $1\le k\le n$,

poly[p_?PrimeQ, n_, x_] := 
 PowerRange[1, x^n, x].# & /@ ({##, 1} & @@@ 
    Tuples[({Range[p - 1], ##} & @@ Table[Range[0, p - 1], {n - 1}])])
poln[p_, n_] := (p - 1) p^(n - 1)


Grid[({#, Column[poly[3, #, s]], poln[3, #]} & /@ Range[1, 3]), 
 Frame -> All]

where the first column is $k$, the second column the desired polynomials and the number of polynomials for degree $k$:

enter image description here


You can do this, it's just that you're going to get a lot of polynomials. If your description of what you want is accurate, it's $(p-1)\times p^{k-1}$ polynomials for each $k$ and add that up for every $k ≤ n$. With $n = 5, p = 7$, you'll get 16806 polynomials. With $n=10, p=11$, the number is $25937424600$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.