Timeline for Are there infinitely many integer-valued polynomials dominated by $1.9^n$ on all of $\mathbb{N}$?
Current License: CC BY-SA 3.0
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Sep 2, 2013 at 20:37 | comment | added | Peter Mueller | @Will Sawin: Those polynomials which have generating function $\sum f(n)x^n=\frac{x^{m-k}(2x-1)^{k-2r}(3x^2-3x+1)^r}{(1-x)^{m+1}}$, where $0\le 2r\le k\le m$. For $m\le49$, there are $k$ (around $0.7m$) and a small $r$ such $\lvert f(n)\rvert\le\tau^n$. | |
| Sep 2, 2013 at 20:11 | comment | added | Will Sawin | @PeterMueller: Interesting! Which family? | |
| Sep 2, 2013 at 13:54 | comment | added | Peter Mueller | @Will Sawin: For each $m\leq49$ there is an integer valued polynomial of degree $m$ and $\lvert f(n)\rvert\le\tau^n$ for all non-negative integers $n$. However, this family doesn't work for larger degrees anymore. | |
| Aug 28, 2013 at 13:16 | comment | added | David E Speyer | @NoamD.Elkies So, how do you find the optimal ratio of exponents? | |
| Aug 28, 2013 at 3:23 | comment | added | Noam D. Elkies | [cont.'d] ... before complaining about loss of precision. For $N \leq 37$ we see only the same four factors, except for a degree-$11$ irreducible in the $N=30$ polynomial; then there are some new factors of degree $\geq 5$ for $38 \leq N \leq 50$, and for $N>50$ it more-or-less breaks down, usually giving just a few factors of $z$, $1-2z$, $1-3z+3z^2$, and sometimes $P_4$, and then a huge residual factor. The neat exception is $N=64$ where we get a pair of degree-$13$ irreducibles. But there might be a tweak that continues giving good factors past $N=50$ and $P_4$. | |
| Aug 28, 2013 at 0:04 | comment | added | Noam D. Elkies | Neat computation. The factor $P_4=1-5z+11z^2-13z^3+7z^4$ is the minimal polynomial of the critical points I found for the optimal $z^k(1-2z)^k (1-3z+3z^2) / (1-z)^{2+2k}$. The exponents $5,9,1,1$ for $z$, $1-2z$, $1-3z+3z^2$, and $P_4$ must be just an approximation to the optimal proportion: even without $P_4$ the optimal ratio is not rational. There's no need to stop at $N=20$: tell gp tau=(sqrt(5)+1)/2; zdif(x)=x-round(x); and then speyer(N, q) = q=(u-tau)^N; forstep(i=N-1,0,-1, q -= zdif(polcoeff(q,i))*(u-tau)^i); round(q) will compute well beyond speyer(20) ... [cont.] | |
| Aug 27, 2013 at 21:52 | history | bounty ended | Vesselin Dimitrov | ||
| Aug 27, 2013 at 16:32 | history | edited | David E Speyer | CC BY-SA 3.0 |
added 859 characters in body
|
| Aug 27, 2013 at 15:52 | comment | added | David E Speyer | I don't know. My vague guess would be no, because the recipe for constructing polynomials below $(\tau+\epsilon)^n$ has so many "large but finite" error terms that I feel like you shouldn't be able to squeeze all the way down to $\tau^n$. But it would certainly be interesting to know! | |
| Aug 27, 2013 at 15:24 | comment | added | Will Sawin | Do you know if there are finitely many integer-valued $f$ such that $f(n) \leq \tau^n$? | |
| Aug 26, 2013 at 21:53 | comment | added | Vesselin Dimitrov | A bounty of 200 will be awarded to this answer in 24 hours. (It turns out that 1) one may not set two bounties of the same worth on the same question, and 2) one has to wait for 24 hours before the bounty can be awarded.) | |
| Aug 26, 2013 at 21:39 | comment | added | Vesselin Dimitrov | In any case, this is amazing. Now I have to award the bounty. Since the solution is a joint one, here is what I will do. I will award the current bounty to Noam Elkies' answer, and start a new bounty of the same worth to reward this complete answer. | |
| Aug 26, 2013 at 21:10 | comment | added | Vesselin Dimitrov | A generalization of Fekete's theorem inspired by arithmetic geometry (and, I think, in a particularly illuminating way) appears in Chinburg's paper "Capacity theory on varieties": archive.numdam.org/ARCHIVE/CM/CM_1991__80_1/CM_1991__80_1_75_0/… See Theorem 1.2 and the Minkowski application in the paragraph following it. | |
| Aug 26, 2013 at 20:50 | comment | added | David E Speyer | @WillSawin Check the update, this problem is solvable for all $r$ and $x$. Fekete's result is that, if $h(x)$ is a monic polynomial with real coefficients, then we can find a a monic polynomial with integer coefficients which is $<1$ on $\{ z: |h(z)|<r \}$. Or, at least, I think that's what the result unpacks to, and I wrote out the argument above for the circle to see if I got it right. | |
| Aug 26, 2013 at 20:41 | comment | added | Will Sawin | So this is a special case of the general problem: Find an integer polynomial which takes values of norm $\leq 1$ on a circle of radius $r<1$ around a real point $x$ in the complex plane. (With $r=A/(A^2-1)$ and $x=A^2/(A^2-1)$) Since it doesn't seem like we are dealing with especially easy $x$, I don't think this will converge to $\tau$ unless the problem is solvable for all $r$ and $x$. But if it were, this would probably be in the literature David Speyer surveyed... | |
| Aug 26, 2013 at 20:01 | history | edited | David E Speyer | CC BY-SA 3.0 |
deleted 8 characters in body
|
| Aug 26, 2013 at 19:45 | comment | added | Noam D. Elkies | You're welcome, and yes I meant $1-3z+3z^2$, not $1-3z+z^2$. (And I was wondering if it might be converging to $\tau$...) | |
| Aug 26, 2013 at 19:36 | history | edited | David E Speyer | CC BY-SA 3.0 |
added 1234 characters in body
|
| Aug 26, 2013 at 18:55 | comment | added | David E Speyer | @NoamD.Elkies Thanks! In the comment above, should $z^2-3z+1$ read $3 z^2 - 3z +1$? | |
| Aug 26, 2013 at 18:42 | comment | added | Noam D. Elkies | The best exponent $k$ in $z^k(1-2z)^k (1-3z+z^2) / (1-z)^{2+2k}$ is not $k=2$ but $k \approx 3.7559$ [it doesn't have to be rational; just use $z^A (1-2z)^A (1-3z+z^2)^B / (1-z)^{2A+2B}$ with $A/B \rightarrow k$]. This gives a bound about $1.68053$, which is the largest root of $x^8 - 7x^6 + 23x^4 - 49x^2 + 49$. One can do better yet by using different multiplicities for the factors $z$ and $1-2z$, which brings the bound down to about $1.656246$. | |
| Aug 26, 2013 at 18:32 | history | edited | David E Speyer | CC BY-SA 3.0 |
added 290 characters in body
|
| Aug 26, 2013 at 17:18 | history | edited | David E Speyer | CC BY-SA 3.0 |
added 14 characters in body
|
| Aug 26, 2013 at 16:57 | history | edited | David E Speyer | CC BY-SA 3.0 |
deleted 78 characters in body
|
| Aug 26, 2013 at 16:33 | history | edited | David E Speyer | CC BY-SA 3.0 |
deleted 51 characters in body
|
| Aug 26, 2013 at 16:23 | history | answered | David E Speyer | CC BY-SA 3.0 |