Timeline for Polynomial representation of sequences of length $n$ taken modulo $m$
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 20, 2013 at 11:34 | comment | added | Emil Jeřábek | Yes, I originally misread the question. I didn’t remove this comment even when I realized this, as I thought it might be useful to point out that the information on AoPS was wrong. | |
| Dec 19, 2013 at 18:52 | comment | added | Victor Wang | Emil: I think you may have misread my question; here I am asking about integer-valued polynomials rather than integer-coefficient polynomials. (I only mentioned the latter as some motivation for considering the former.) Regarding the AoPS thread: the first 2 solutions only address the OP, which deals only with $p,p^2$ (so not $n=8$). The third (OldMath) indeed fails for $k\ge p+1$. The fourth (mine) gives a correct method for all $k$. In a previous (MO) comment I noted that Newton interpolation doesn't apply as directly for the problem at hand (but it still helps a lot). | |
| Dec 19, 2013 at 10:56 | comment | added | Emil Jeřábek | I’m afraid even the case $n=m$ is more complicated than the AoPS thread suggests, the solution given there is incorrect. For instance, for $n=8$ they claim that the ideal of integer polynomial vanishing mod 8 is $\langle8,4(x^2-x),2(x^2-x)^2,(x^2-x)^3\rangle$, and that there are $2^{12}$ sequences (functions on $\mathbb Z/8\mathbb Z$) representable by polynomials, whereas in reality, the ideal is $\langle8,4(x^2-x),x(x-1)(x-2)(x-3)\rangle$, and the number of sequences is $2^{10}$. | |
| Dec 18, 2013 at 22:13 | history | edited | Victor Wang | CC BY-SA 3.0 |
(*) is apparently italics (?), so changed (*) to (+)
|
| Jul 15, 2012 at 23:53 | history | edited | Victor Wang | CC BY-SA 3.0 |
explicit base case (j=1) proof, didn't realize it was somewhat difficult
|
| Jul 15, 2012 at 23:02 | history | edited | Victor Wang | CC BY-SA 3.0 |
a couple of typos
|
| Jul 15, 2012 at 22:09 | history | edited | Victor Wang | CC BY-SA 3.0 |
\mathbb{F}_p behaving badly
|
| Jul 15, 2012 at 16:47 | comment | added | Victor Wang | By Newton interpolation, one can easily determine the number and structure (the latter to a lesser extent) of sequences $(a_1,a_2,\ldots,a_n)\pmod{n}$ represented by integer polynomials nicely given the prime factorization of $n$ (esp. for prime powers). However, for such $f$ we have restrictions like $u-v\mid f(u)-f(v)$ for integers $u,v$. IMO it's then natural to wonder about (e.g. the new structure of valid $f$) for rational polynomials in general. Standard interpolation methods aren't as clean, and I don't see a clear connection between sequences and their polynomial representations. | |
| Jul 15, 2012 at 15:33 | comment | added | tweetie-bird | I'm curious what's the motivation for this question? | |
| Jul 15, 2012 at 15:09 | history | edited | Victor Wang | CC BY-SA 3.0 |
fixed a minor error in the case where n,m are not powers of the same prime
|
| Jul 15, 2012 at 1:02 | history | edited | Victor Wang | CC BY-SA 3.0 |
clarified order of (0,...,0)
|
| Jul 14, 2012 at 22:52 | history | asked | Victor Wang | CC BY-SA 3.0 |