Timeline for Number of nonzero terms in polynomial expansion (lower bounds)
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 23, 2015 at 18:54 | answer | added | Boris Bukh | timeline score: 5 | |
| Jul 23, 2015 at 13:49 | vote | accept | Lucas Perin | ||
| Jul 19, 2015 at 10:07 | answer | added | Richard Stanley | timeline score: 12 | |
| Jul 18, 2015 at 19:06 | comment | added | Gabriel Dill | Arithmetic progressions give indeed the lowest possible number of terms if one considers only case 1: Assume $z_1 < z_2 < \dots < z_k$. Then the $m(k-1)$ numbers $z_{i,j} = iz_{j+1}+(m-i)z_j$ ($i=0,\dots,m-1$, $j=1,\dots,k-1$) are all different from each other and from $z_{0,k}=mz_k$, since $z_{i,j} < z_{i+1,j}$ and $z_{m-1,j} < z_{0,j+1}$ for all $i$ and $j$. | |
| Jul 18, 2015 at 15:58 | history | edited | Lucas Perin |
Added number theory tag
|
|
| Jul 18, 2015 at 15:56 | comment | added | Lucas Perin | Yes, this is a good observation. I suppose I should mention now that $q=p$ and $1 \le m \le p-1$. So the freshman's dream does not help me. Also, I'll need to consider that some polynomial $P(x) = f(x) + a_0$ where $P$ is irreducible over $\mathbb{F}_q$. But this would make my question too extensive and hard, so I'll leave it as a comment for now. | |
| Jul 18, 2015 at 14:33 | comment | added | Gabriel Dill | A trivial observation concerning case 2: If $q=p^e$ for a prime $p$ and $m=p^l$ ($l \geq 0$), then $f(x)^m$ will have the same number of nonzero terms as $f(x)$, since $(x+y)^p = x^p+y^p$ in characteristic $p$. So unless you exclude $m=p^l$, you can't hope for a lower bound greater than $k$. | |
| Jul 18, 2015 at 5:21 | history | edited | Lucas Perin | CC BY-SA 3.0 |
improved case 2, added mod equivalence.
|
| Jul 18, 2015 at 5:16 | comment | added | Lucas Perin | @DavidSpeyer I was not familiar with this theorem, this means that I may generalize the number of terms (considering case 1 only) as $mk - (m-1)$, correct? Also, could you elaborate on the "roughly optimal"? | |
| Jul 18, 2015 at 5:05 | history | edited | Lucas Perin | CC BY-SA 3.0 |
improved question using comments
|
| Jul 18, 2015 at 4:42 | history | edited | Lucas Perin | CC BY-SA 3.0 |
improved question
|
| Jul 18, 2015 at 4:03 | history | edited | Lucas Perin | CC BY-SA 3.0 |
fixed exponent in first example
|
| Jul 18, 2015 at 3:44 | history | edited | Lucas Perin | CC BY-SA 3.0 |
quick fix. Upper bound should be m+k not m-k
|
| Jul 18, 2015 at 2:07 | comment | added | David E Speyer | This is vaguely reminiscent of Frieman's theorem en.wikipedia.org/wiki/Freiman%27s_theorem . If there is no cancellation in expanding your power, then Frieman tells you that taking your terms in an arithmetic progression is roughly optimal. I hope that someone comes along with a better answer soon. | |
| Jul 17, 2015 at 17:09 | history | asked | Lucas Perin | CC BY-SA 3.0 |