User noam d. elkies - MathOverflow

Answer by Noam D. Elkies for Sequences equidistributed modulo 1

2013-05-18T03:33:22Z

Let $s_n = 2^n$ and choose for $a$ any real number that's normal in base $2$.

Answer by Noam D. Elkies for Elliptic curves over QQ with identical 13-isogeny

2013-05-16T15:33:28Z

[Edited mostly to include the second example, corresponding to $(t,X) = (3,-115/126)$]

Thanks to Jordan Ellenberg for calling attention to this nice question on his blog. I didn't remember an example in my "private archive", but the question is close enough to some of my previous computations that I was able to adapt those techniques here. It turns out that there are infinitely many such pairs (even up to quadratic twist); one example has both torsion subgroups defined over the 7th cyclotomic field ${\bf Q}(\zeta_7)$: the curve with coefficients $[0,-1,1,-2,-1]$, i.e. $y^2 + y = x^3 - x^2 - 2x - 1$, of conductor $147 = 3 \cdot 7^2$ and discriminant $-147$, and the curve with coefficients $$ [0,-1,1,-1424883795842044404862,-20702237422068075268318817670099], $$ conductor $8480886141 = 3 \cdot 7^2 \cdot 13 \cdot 251 \cdot 17681$, and discriminant $3 \cdot 7^2 13^{13} 251^{13} 17681$. This felt familiar, and it turns out that I had already encountered the quadratic twists of these curves by ${\bf Q}(\sqrt{-7})$ because one of them, also of conductor $3 \cdot 7^2$ but discriminant $-3 \cdot 7^8$, is the Jacobian of the Shimura modular curve computed in my paper

Elkies, N.D.: Shimura Curves for Level-3 Subgroups of the $(2,3,7)$ Triangle Group, and Some Other Examples, Lecture Notes in Computer Science 4076 (proceedings of ANTS-7, 2006; F.Hess, S.Pauli, and M.Pohst, ed.), 302$-$316; arXiv:math/0409020.

(so it was already in my "public archive"...). See page 11 of the arXiv version: Mark Watkins noted that this curve 147-B1(I) actually has 13-torsion over the cubic field ${\bf Q}(\zeta_7^{\phantom1} + \zeta_7^{-1})$; I then explained this observation from the Shimura-curve structure, and noted (footnote 5) that the twist of $X_1(13)$ parametrizing curves over ${\bf Q}$ with a $13$-torsion point over ${\bf Q}(\zeta_7^{\phantom1} + \zeta_7^{-1})$ has at least one more orbit of rational points, which yields the curve of conductor $8480886141$.

As Jordan observes in his blog, and also in his comment here, the question of finding pairs of curves with "the same" cyclic $13$-isogeny is equivalent to finding rational points (away from some degeneracy locus) on a certain surface $S$. This surface turns out to be "honestly elliptic" of the simplest kind (with $\chi=3$): the canonical class $K_S$ is positive but not ample, with a two-dimensional space of sections that gives a map $S \rightarrow {\bf P}^1$ whose fibers are curves of genus $1$. This fibration has sections defined over ${\bf Q(i)}$ but not over ${\bf Q}$. But many of the first few fibers have rational points small enough to find by a brief computer search. Any one such point yields infinitely many rational points on its fiber, and thus infinitely many pairs of $j$-invariants of elliptic curves with Galois-isomorphic subgroups of order $13$.

The surface has a birational model $ Y^2 = (X^2+4) A(X), $ where $A(X)$ is the quadratic $A_2 X^2 + A_1 X + A_0$ whose coefficients $A_2,A_1,A_0$ are the following sextics in $t$: $$ A_2(t) = t^6-4t^5+6t^4-2t^3+t^2-2t+1, $$ $$ A_1(t) = -6t^5+26t^4-22t^3-4t^2+6t, $$ $$ A_0(t) = 4t^6-8t^5+37t^4-74t^3+57t^2-16t+4. $$ Thus we have for each $t$ a curve of genus $1$, though without an obvious rational point (except for the degenerate $t=0,1,\infty$ where every $X$ makes $(X^2+4) (A_2(t) X^2 + A_1(t) X + A_0)$ a square but the resulting elliptic curves $E,E'$ are isomorphic). So I tried a few small values of $t$ with Stahlke and Stoll's program ratpoints. For $t=2$ the program reported an obstruction, and indeed there's no $11$-adic solution. Hence our elliptic fibration has no section over ${\bf Q}$ (else we could specialize it at $t=2$), though there are certainly sections over ${\bf Q}(i)$, namely $X=\pm 2i$ (and also the roots of $A(X)$). Still we can look for rational points on individual fibers, and we already succeed for $t=3$, finding a rational solution at $X=-115/126$, and several solutions of larger height for other small $t$. An hour's exhaustive search up to height $50$ for $t_0$ and $500$ for $X$ finds three further solutions, including $(t,X) = (33/17,0)$ which leads to the curves of conductor $147$ and $8480886141$ exhibited above. The solution $(t,X) = (3,-115/126)$ corresponds to the curves $$ [1, 1, 0, -2193228435814, -4048327365374399852], $$ with conductor $133333589432694 = 2 \cdot 3 \cdot 7 \cdot 181^2 \cdot 263 \cdot 607^2$, and $$ [1, 1, 0, -9358273692452696799, -11018986378569871927950945915], $$ with conductor $N = 18612166837338258 = 2 \cdot 3 \cdot 79 \cdot 181^2 \cdot 607^2 \cdot 3253$ (these curves were recovered from their $j$-invariants using J.Cremona's conductor-minimizing Sage routine EllipticCurve_from_j); both curves have $x$-coordinates in the same cubic field of discriminant $181^2 607^2$, and $y$-coordinates in the quadratic extension of that field by $\sqrt{-181 \cdot 607}$.

Details of the computation of the surface etc. coming soon (but probably in a separate answer because this is already quite long or a Mathoverflow answer...).

Answer by Noam D. Elkies for Contest problems with connections to deeper mathematics.

2011-07-07T19:56:17Z

[Found another of these Putnam problems; it seems that the protocol here is to post separate big-list examples separately rather than add them to one big-answer.]

2002 Problem B-6. Let $p$ be a prime number. Prove that the determinant of the matrix $$ \left(\begin{array}{lll}x&y&z\cr x^p &y^p&z^p\cr x^{p^2}&y^{p^2}&z^{p^2}\end{array}\right) $$ is congruent modulo $p$ to a product of polynomials of the form $ax+by+cz$ where $a,b,c$ are integers.

This actually works for the analogous $n\times n$ determinant for each $n$, and also over any finite field $k$ rather than just the prime field $\mathbb{Z} / p \mathbb{Z}$. The case $n=2$ is basically Fermat's little theorem; the general case is Moore's $q$-analogue of the Vandermonde determinant, used by Dickson to find the subring of $k[x_1,\ldots,x_n]$ invariant under all $k$-linear transformations of the $x_i$: they're the polynomials in $n$ fundamental invariants of degrees $q^n - q^i$ ($i=0,1,2,\ldots,n-1$), with the invariant of degree $q^n-1$ being the $q-1$ power of the Moore determinant. Moreover, replacing that power with the Moore determinant itself yields the invariants for $SL_n(k)$ instead of $GL_n(k)$. This century-old theorem has found applications ranging from algebraic topology to Diophantine and algebraic geometry.

References:

E.H.Moore: A two-fold generalization of Fermat's theorem, Bull. AMS 2 #7 (1986), 189-199.

L.E.Dickson: A fundamental system of invariants of the general modular linear group with a solution of the form problem. Trans. AMS 12 (1911), 75-98

Answer by Noam D. Elkies for cube + cube + cube = cube

2013-05-05T18:39:17Z

JHI's elegant lower bound of $8$ on $N$ is achieved by an explicit dissection. I show my construction below; you might want to try to find a solution yourself before proceeding $-$ it makes for a neat puzzle. There may well be other ways to do it.

If somebody can make a "$3$-dimensional" graphic or picture of the $8$-piece dissection, you're welcome to add it by editing my answer. My diagrams are two-dimensional, labeling each piece with its height. Fortunately the dissection is simple enough for this to be possible; in particular, the eight pieces comprise four boxes and four L-shaped prisms. This also made it possible to find the solution using just pencil and paper on an otherwise uneventful international flight.

Begin by cutting the $6 \times 6 \times 6$ cube top to bottom into three pieces, as shown in top view in the first square diagram. Then cut each piece horizontally in two, dividing AB into $3+3$,$\phantom.$ C into $4+2$, and D into $5+1$. Each AB piece is then further subdivided into a box B and an L-shaped prism A. The second diagram shows (say) the bottom layer of four pieces, and the third diagram shows the top. Note that the AB subdivisions are not quite the same.

Pieces with the same color will come together to form a smaller cube. The larger C piece is a $4$-cube, and the two A pieces form a $3$-cube as shown. It remains to construct the $5$-cube from the remaining five pieces. The last two diagrams show the bottom and top of the $5$-cube.

The two $5$'s are the larger B piece, rotated to span the entire height of the cube, and the thick D piece. The thin D piece completes the bottom, with width $1$. The top is filled by the thinner C piece and the smaller B, both rotated to height 4. QEF

I guess that a physical model won't make for a hard puzzle to reconstitute into either one or three cubes (e.g. the AB, C, and D parts of the $6$-cube are independent) but would still make a nice physical model of the identity $3^3 + 4^3 + 5^3 = 6^3$.

This dissection is specific to the solution $(a,b,c;d)=(3,4,5;6)$ of the Diophantine equation $a^3+b^3+c^3=d^3$; I don't know whether an $8$-piece dissection is possible for any other solution. JHI's analysis shows that one can never get below $8$, and in some cases even that's not possible: if $a<b<c$ and $a+c<d$ then there's at least one corner of the $d$-cube, say $(1,1,1)$, that contributes to the $a$-cube, but then any cell $(x,y,z)$ with $\max(x,y,z) = a+1$ cannot connect to any corner. This first happens for $(a,b,c;d) = (6,32,33;41)$.

What's the minimal dissection for the "taxicab" identity $1^3 + 12^3 = 9^3 + 10^3$? JHI's corner-cutting argument shows that at least nine pieces are needed.

Answer by Noam D. Elkies for The integral inequality

2013-04-25T18:06:05Z

No, such an inequality need not hold: one can construct $f$ of exponential type and a sequence ${a_n}$ of real numbers such that $$ \frac1{f(a_n)} \int_{a_n - \frac12}^{a_n - \frac12} \left|\phantom.f(x)\right|\phantom. dx \rightarrow 0. $$ Indeed if ${a_n}$ increases rapidly enough then the growth of $f$ can be arbitrarily slow given that $f$ cannot be a polynomial; for example, taking $a_n = 10^n$ in the construction below makes $$ f(z) \ll \exp\left(B \phantom. \log^2 (1+\left|z\right|)\right) $$ for some absolute constant $B$ (and all $z \in {\bf C}$).

(The following construction spells out what's in Fedja's and my comments, but neither of us got around to writing it up two months ago, and now mathoverflow brought it back to the front of the queue, presumably for lack of an upvoted or accepted answer.)

The idea is to make $f(a_n)$ smaller than usual given the growth of $f$, but still larger than its average on $\left|x-a_n\right| \leq \frac12$, due to $n$-th order zeros at the edge of that interval. If $a_n \rightarrow\infty$ fast enough then $f$ can still have exponential or even much slower growth.

Let $\lbrace a_n \rbrace$, then, be a rapidly growing sequence, say $a_n = 10^n$; and define $f$ as the real Weierstrass product $f = \prod_{m=1}^\infty f_m^m = f_1 \phantom. f_2^2 \phantom. f_3^3 \phantom. f_4^4 \cdots $ where $$ f_m(x) = \Bigl( 1 - \frac{x}{a_m - \frac12} \Bigr) \phantom. \Bigl( 1 - \frac{x}{a_m + \frac12} \Bigr) $$ is the quadratic polynomial with roots at $a_m \pm 1/2$ such that $f_m(0) = 1$. Even with the growing multiplicities of the roots of $f$, the zeros are sparse enough to assure convergence and slow growth of the product.

Now for large $n$, if we restrict $x$ to $\left|x-a_n\right| \leq \frac12$ then all the factors $f_m^m$ for $m\neq n$ are essentially constant on that interval, so $f(x)$ is very nearly $\phantom.f(a_n)\phantom. \left(\phantom.f_n(x)\left/f_n(a_n)\right.\right)^n$. Thus $$ \frac1{f(a_n)} \int_{a_n - \frac12}^{a_n - \frac12} \left|\phantom.f(x)\right|\phantom. dx \sim \int_{a_n - \frac12}^{a_n - \frac12} \left(\frac{f_n(x)}{f_n(a_n)}\right)^n \phantom. dx = \int_0^1 \bigl(4u(1-u)\bigr)^n \phantom. du, $$ where $u = x - (a_n - \frac12)$. The integral is $(2^n n!)^2 \left/ (2n+1)! \right. = O(n^{-1/2}) \rightarrow 0$, QED.

Answer by Noam D. Elkies for Numbers integrally represented by a ternary cubic form

2013-04-11T23:27:57Z

Your conjectures are correct. So was the "someone else at MSRI [who] muttered something about norm forms" (mentioned in earlier edits of the question), except for the part about laughing at you.

As you in effect note, $f(a,b,c)$ is the norm $N_{K/{\bf Q}}(a+bx+cx^2)$, where $x$ is one of the roots of $x^3-x^2-x-1 = 0$ and $K$ is the cubic number field ${\bf Q}(x)$. This field has discriminant $-44$, and ${\bf Z}[x]$ is the full ring of integers $O_K$ (equivalently, the field discriminant of $K/{\bf Q}$ equals the polynomial discriminant of $x^3-x^2-x-1$; to check this in gp, compute

poldisc(x^3-x^2-x-1)
nfdisc(x^3-x^2-x-1)

and observe that both return $-44$). Now for (A), you already know that $x^3-x^2-x-1$ has at least one root modulo any prime $q$ unless $q$ is represented by the nonprincipal quadratic form $3u^2+2uv+4v^2$ of discriminant $-44$. (For other $q$: there's a triple root for $q=2$, a double and a simple root for $q=11$, three distinct roots for $q=u^2+11v^2$, and one simple root for odd $q$ not congruent to a square $\bmod 11$.) Equivalently, $K$ has an ideal of norm $q$ unless $q = 3u^2+2uv+4v^2$. But $O_K$ is a principal ideal domain, so once there's an ideal of norm $q$ then it has a generator $a+bx+cx^2 \in O_K$, and then $q=f(a,b,c)$ (or $q=f(-a,-b,-c)$ if we chose $a+bx+cx^2$ of norm $-q$). The discriminant of $K$ is small enough that one can check unique factorization by hand using the Minkowski bound; nowadays this exercise can also be done routinely on the computer, e.g. in gp

K = bnfinit(x^3-x^2-x-1); K.cyc

(This functionality happens to be one of the "Usage examples" in the current Wikipedia page on gp.)

[EDIT In fact this $K$ happens to be one of the handful of number fields whose Minkowski bound is so tight that nothing needs to be checked! The discriminant $\Delta_K = -44$ is small enough in absolute value that the bound $$ \frac4\pi \frac{3!}{3^3} \left|\Delta_K\right|^{1/2} = 1.8768\ldots $$ is less than $2$, which means every ideal $I$ has a nonzero element of norm $\pm \left|I\right|$ and is thus automatically principal. TIDE]

(B) Translating the factorization of $x^3-x^2-x-1 \bmod q$ into the factorization of the ideal $(q)$ in $O_K$, we see that if $q = 3u^2+2uv+4v^2$ then $(q)$ remains prime in $O_K$, and thus that $q \mid N_{K/{\bf Q}}(a+bx+cx^2)$ iff $q \mid a+bx+cx^2$. For $q=2$ the ideal $(q)$ is the cube of $(1+x)$, so $8 \mid f(a,b,c)$ iff $a,b,c$ are all even. Any power of a prime $q$ other than those of the form $3u^2+2uv+4v^2$ can be represented primitively by $f$, even $q=11$ (for which $(q)$ factors as $(2+x)(3-2x)^2$). If we do not care about primitivity then we can also represent all powers of $2$, and all powers of $q^3$ for $q = 3u^2+2uv+4v^2$.

By multiplicativity this also proves the final conjecture: the nonzero $n \in {\bf Z}$ that are represented by $f$ are precisely those whose $q$-valuation is a multiple of $3$ for all primes $q = 3u^2+2uv+4v^2$.

Answer by Noam D. Elkies for Characterise all pairs of n/m stars that have the same inner radius

2013-04-08T05:03:54Z

[Expanding some on my comment of a few days ago]

This is a special case of a problem that was solved by Gerrit Bol in 1936 [B]; that nearly-forgotten result was rediscovered, using slightly different methods, by Bjorn Poonen and Michael Rubinstein [PR]. (As it happens I used such coincidences in my own work a few years ago [E].) They find all ways that three diagonals of a regular polygon can meet at a point: there are several infinite families (comprising algebraically "trivial" solutions that are not always geometrically obvious, plus the four "nontrivial" families of Table 3 on page 12), and 65 sporadic solutions (Table 4 on page 13). If two stars have the same inner and outer radii then we can rotate them so they share an inner vertex; then the outer vertices are contained among the vertices of a regular polygon, and the shared inner vertex is on at least four diagonals $-$ indeed at least five if we include the line of symmetry (and double the order of the regular polygon if necessary). Four infinite families (all symmetrical) of such quintuple intersections are listed in Table 6 (page 16), and a finite computation limits further sporadic solutions to denominators 18, 24, and 30 (pages 15-16). If you've already computed far enough to find any sporadic solutions then the infinite families must account for everything else.

References

[B] Gerrit Bol: Beantwoording van prijsvraag no. 17, Nieuw Archief voor Wiskunde 18 (1936), 14-66.

[PR] Bjorn Poonen and Michael Rubinstein: The Number of Intersection Points Made by the Diagonals of a Regular Polygon, SIAM J. Discrete Math 11 (1998), 135-156 (http://www-math.mit.edu/~poonen/papers/ngon.pdf).

[E] Noam D. Elkies: On some points-and-lines problems and configurations, Periodica Mathematica Hungarica 53 #1-2 (2006), 133-148 (arXiv:MG/0612749).

Answer by Noam D. Elkies for sum of three cubes and parametric solutions

2013-04-07T05:52:47Z

Seeing that the link is to a 1996 announcement that I posted to sci.math.research, I suppose I should explain. Yes, the formulation in that announcement is not clearly stated $-$ one doesn't polish USENET posts like a published paper, and can't even edit after the fact (as is possible on mathoverflow) to correct blatant typos like the stray "+1" in the formula "(x,y,z)=(1+6t^3+1,1-6t^3,-6t^2)".
As it happens here there is a published paper that appeared only a few years later:

Elkies, Noam D.: Rational points near curves and small nonzero $|x^3-y^2$| via lattice reduction, Lecture Notes in Computer Science 1838 (proceedings of ANTS-4, 2000; W.Bosma, ed.), 33-63 (arXiv:math.NT/0005139).

but the relevant section (3.2) doesn't address parametrizations of $x^3+y^3+z^3=2$. The answer to the present question is that D.Burde is basically right: the correct statement was, and still is, that all known solutions of $x^3 + y^3 + z^3 = 2$ in ${\bf Q}[t]$ come from the identity $$ (1+6t^3)^3 + (1-6t^3)^3 + (-6t^2)^3 = 2 $$ by permuting $x,y,z$ and substituting some polynomial for $t$. The substitution need not be linear, but nonlinear substitutions like $(x,y,z) = (1+6t^6, 1-6t^6, -6t^4)$ give no new $(x,y,z)$ solutions either. I don't think any method is known that would prove that there are no other nonconstant solutions, or that there's no nonconstant solution in ${\bf Q}(t)$ to $x^3+y^3+z^3=d$ unless $d$ is a cube or twice a cube. All that can be said is that if there were such a solution that had small enough degree and coefficients then it would have turned up in searches for integral solutions such as the searches described in that ANTS-4 paper and also on this page.

Answer by Noam D. Elkies for More expanders?

2013-03-24T02:37:38Z

Freddie Manners is right: graphs (1) and (2) are not expanders for any choice of $g$. For (1), he already showed this by exhibiting large vertex sets with $O(1)$ neighbors. For (2) we prove it below by contructing vectors $v$ orthogonal to the all-$1$ vector for which the Rayleigh quotient $\langle Av, v \rangle / \langle v, v \rangle$ is within $o(1)$ (indeed $O(1/n)$) of the graph degree, thus proving that there is no spectral gap. Graph (3) is probably an expander, because the maps taking $z$ to $z^{-1}$ and $z+2$ generate a congruence subgroup of index 3 in ${\rm PSL}_2({\bf Z})$ (as Serre notes in the very last section of A Course in Arithmetic), and the graph vertices can be identified with an orbit of cusps of a modular curve of level $2^n$, so one should be able to use the $3/16$ bound on that curve; but I'll leave that to the folks who actually know these techniques.

For (2): let $k$ be a finite field of $2^n$ elements, and consider the graph where each $z$ is adjacent to $gz$ $-$ and thus also to $g^{-1} z$ $-$ and to $z+e$. Fix a nontrivial homomorphism $\epsilon$ from $(k,+)$ to the group $\lbrace\pm1\rbrace$; the usual choice is $\epsilon(x) = (-1)^{{\rm Tr}(x)}$. Then for each $c \in k$ we have a homomorphism $\epsilon_c: (k,+) \rightarrow \lbrace\pm1\rbrace$ defined by $\epsilon_c(x) = \epsilon(cx)$, and these $\epsilon_c$ form an orthonormal basis for the Euclidean space of real-valued functions on $k$ with inner product $$ \langle f, g \rangle := \frac1{2^n} \sum_{x\in k} f(x) g(x). $$ So we're seeking a linear combination of the $\epsilon_c$ with $c \neq 0$ that is almost fixed by the adjacency matrix $A$ in the sense that $\langle Av, v \rangle / \langle v, v \rangle = 3 - O(1/n)$.

Write $A = A_1+A_2$ where $A_1$ is induced by translation by $e$ and $A_2$ is induced by multiplication by $g^{\pm 1}$. Then for each $c \in k$ we have $A_1 \epsilon_c = \epsilon(ce) \epsilon_c$ and $A_2 \epsilon_c = \epsilon_{gc} + \epsilon_{g^{-1}c}$. We shall take $v = \sum_{i=1}^{n-1} \epsilon_{g^i c}$ for some $c\neq 0$, so $\langle v, v \rangle = n-1$ and $\langle A_2 v, v \rangle = 2n-4$. We next show that $c$ can be chosen so that $v$ is an eigenvector of $A_1$, corresponding to the eigenvalue $1$. Because $\lbrace c : \epsilon(ce) = +1 \rbrace$ is a $({\bf Z}/2{\bf Z})$-subspace of $k$ of codimension $1$, the same is true of $\lbrace c : \epsilon(g^i ce) = +1 \rbrace$ for each $i$, so the intersection of these $n-1$ subspaces has positive dimension. Choosing nonzero $c$ in this intersection makes $A_1 v = v$ as claimed. Then $$ \langle A v, v \rangle = \langle A_1 v, v \rangle + \langle A_2 v, v \rangle = (n-1) + (2n-4) = 3n-5 = (3-O(1/n)) \langle v, v \rangle, $$ QED.

Exercise: Adapt this technique to show that the graph on ${\bf Z} / p {\bf Z}$ where each $z$ is connected to $z \pm 1$ and $g^{\pm 1} z$ is not an expander either for any $g \in ({\bf Z} / p {\bf Z})^*$. (That's what I first thought graph (1) was when I quickly read the question.)

Answer by Noam D. Elkies for Subfield of rational function field and which is not a rational function field

2013-03-15T03:27:00Z

This is essentially the question of whether a $k$-unirational variety is necessarily $k$-rational. The short answer is No. The following longer answer mostly summarizes some of the exposition at http://en.wikipedia.org/wiki/Rational_variety; for more information see that page and the references it gives.

The existence of a non-rational subfield $F$ of $K$ depends on $k$ and $n$. If $k$ is algebraically closed and of characteristic zero, then the answer is No for $n=2$ by a theorem of Castelnuovo (and for $n=1$ by a theorem of Lüroth), but Yes for $n=3$, and thus for all $n \geq 3$ (you did not require $F/K$ to be a finite extension). In characteristic $p>0$ things can get much stranger: Zariski gave examples for $n=2$ where the extension $K/F$ is inseparable; and more recently Shioda constructed, for each $n \geq 2$ and every power $q$ of $p$, an example where $K/F$ is inseparable and $F$ is the function field of the Fermat hypersurface of dimension $n$ and degree $q+1$ (which is of general type once $q \geq n+3$), see Propositions 1 and 3 in

Shioda, T.: An Example of Unirational Surfaces in Characteristic $p$, Math. Ann. 211 (1974), 233-236.

Answer by Noam D. Elkies for long enough interval of integers to solve a simultaneous congruence

2013-03-05T17:04:53Z

[Edited again mostly to spell out why the $m_j \bmod a$ are distinct.]

Yes, the desired result is true for all $k$. The following proof is elementary but possibly more algebraic than expected (apparently some kind of variant of the "polynomial method" in combinatorics, though with no need for anything as advanced as the "combinatorial Nullstellensatz"). This would make for a good Putnam B-6 problem; indeed I wouldn't be surprised if this question has already been used for such a competition.

Let $a_1,\ldots,a_k$ be pairwise coprime positive integers, and set $a = \prod_{i=1}^k a_i$. For each $i$ let $A_i$ be a nonempty subset of ${\bf Z} / a_i {\bf Z}$, and let $Z_i$ be the complement of $A_i$ in ${\bf Z} / a_i {\bf Z}$. Let $A \subseteq {\bf Z} / a {\bf Z}$ consist of the residues $n \bmod a$ such that $n \bmod a_i \in A_i$ for each $i$. Let $Z$ be the complement of $A$ in ${\bf Z} / a {\bf Z}$, consisting of the residues $n \bmod a$ such that $n \bmod a_i \in Z_i$ for some $i$.

We claim:

Proposition. This set $Z$ cannot contain a run of $$ N := \prod_{i=1}^k (a_i - |A_i| + 1) = \prod_{i=1}^k (|Z_i| + 1) $$ consecutive residues $\bmod a$.

Proof: Let $w \in {\bf C}$ be a primitive root of unity of order $a$, so that $w_i := w^{a/a_i}$ is a primitive root of unity of order $a_i$ for each $i$. Set $W_i := \lbrace w_i^n | n \in Z \rbrace$, a set of size $|Z_i|$, and $P_i(X) := \prod_{x \in W_i} (X-x)$, which is thus a polynomial of degree $|Z_i|$. Then for any $n \bmod a$ we have $n \in Z$ iff $$ 0 = \prod_{i=1}^k P_i(w_i^n) = P(w^n), $$ where $P$ is the polynomial defined by $$ P(X) := \prod_{i=1}^k P_i(X^{a/a_i}). $$ Because each $P_i(X^{a/a_i})$ is the sum of at most $|Z_i|+1$ monomials, their product $P$ is the sum of at most $\prod_{i=1}^k (|Z_i|+1) = N$ monomials, say $$ P(X) = \sum_{j=1}^N c_j X^{m_j}. $$ The $N$ exponents $m_j$ are the integers of the form $a \sum_{i=1}^k b_i/a_i$ with $0 \leq b_i \leq |Z_i|$. Since each $|Z_i| < a_i$ (this is where we use the hypothesis $A_i \neq \emptyset$) and the $a_i$ are pairwise coprime, it follows that these $m_j$ have pairwise distinct residues $\bmod a$.

We claim, then, that for each $n \bmod a$ at least one of $P(w^n), P(w^{n+1}), \ldots, P(w^{n+N-1})$ is nonzero. Suppose not. Then $(c_1,\ldots,c_N)$ would be a nonzero solution of the $N \times N$ linear system $$ \sum_{j=1}^N w^{m_j (n+k)} c_j = 0 \phantom{\infty} (k=0,1,\ldots,N-1). $$ Hence $(w^{-nm_1^{\phantom.}} c_1^{\phantom.}, \ldots, w^{-nm_N^{\phantom.}} c_N^{\phantom.})$ would be a nonzero vector in the kernel of the Vandermonde matrix with entries $(w^{m_j})^k$. But then some two $w^{m_j}$ would coincide, contradicting our observation that the residues $m_j \bmod a$ are distinct. This completes the proof.

P.S. Note that we do not even need the formula for the determinant of a Vandermonde matrix, only the fact that it is invertible, which can be obtained by interpreting the kernel of the transposed matrix as the space of polynomials of degree less than $N$ that vanish at the $N$ distinct points $w^{m_j}$.

Answer by Noam D. Elkies for Best results regarding the Lang-Trotter conjecture

2013-02-14T22:30:02Z

A couple of years after my Ph.D. thesis (whose main result is the infinitude of singular primes, i.e. $P(x) \rightarrow \infty$ as $x \rightarrow \infty$), Kaneko published a result[1] that let me obtain the unconditional upper bound[2] $P(x) = O(x^{3/4} \log x)$ using some of the same ideas:

[1] Masanobu Kaneko: Supersingular $j$-invariants as singular moduli mod $p$, Osaka J. Math. 26 (1989), 849–855.

[2] Noam D. Elkies: Distribution of supersingular primes, Astérisque 198-199-200 (1991; proceedings of Journées Arithmétiques 1989), 127–132.

As noted in [2], the factor $\log x$ can be removed with some more care (averaging over the auxiliary discriminants $-D$ improves on the worst-case estimate), thus exactly matching Serre's conditional bound.

As far as I know, no further improvement has been obtained since then, even assuming GRH.

That paper [2] also reports lower bounds from my thesis, conditional on GRH for quadratic characters: $P(x) \gg \log \log x$, and also $P(x_n) \gg \log x_n$ for an infinite sequence $x_n \rightarrow \infty$.

Answer by Noam D. Elkies for fourier analytic proofs

2013-02-02T16:40:21Z

The sign of the quadratic Gauss sum $\tau$ can be obtained from the spectrum of the discrete Fourier transform $\Phi$: the trace of $\Phi$ gives $\tau$, and $\det\Phi$ distinguishes $\tau$ from $-\tau$.

Recall that for an odd prime $p$ the quadratic Gauss sum can be defined by $$ \tau = \sum_{n=0}^{p-1} \zeta^{n^2} $$ where $\zeta = e^{2\pi i / p}$. It is elementary that $|\tau|^2 = p$ and that $\tau$ is real or pure imaginary according as $p \equiv 1 \bmod 4$ or $p \equiv -1 \bmod 4$. In fact $\tau$ is always $+\sqrt p$ in the former case, and $+i\sqrt p$ in the latter, but this is notoriously tricky to prove.

One trick is to recognize $\tau$ as the trace of the discrete Fourier transform on ${\bf C}^p$, which has matrix $$ \Phi = (\zeta^{mn})_{m,n=0}^{p-1}. $$ Now $\Phi^2$ is the matrix whose $(m,n)$ entry is $p$ if $m+n \equiv 0 \bmod p$ and $0$ otherwise (this is tantamount to discrete Fourier inversion). This matrix has eiganvalues $+1$ and $-1$ with multiplicity $(p+1)/2$ and $(p-1)/2$ respectively. Hence $\Phi$ has eigenvalues $i^k \sqrt p$ ($k=0,1,2,3$) with multiplicities $m_k$ satisfying $m_0 + m_2 = (p+1)/2$ and $m_1 + m_3 = (p-1)/2$, and then $\tau = \sum_{k=0}^3 m_k i^k \sqrt p$. Since we already know $\tau$ up to sign there are only two possibilities: if $p \equiv 1 \bmod 4$ then $m_0$ or $m_2$ is $(p+3)/4$ and the other three $m_k$ are $(p-1)/4$, while if $p \equiv -1 \bmod 4$ then $m_1$ or $m_3$ is $(p-3)/4$ and the other three $m_k$ are $(p+1)/4$. We are to show that the odd man out is always $m_0$ in the former case and $m_3$ in the latter.

In each case we can decide the correct choice by computing the sign (a.k.a. argument) of $\det \Phi = p^{p/2} \prod_{k=0}^3 i^{k m_k}$. We can do this because $\Phi$ is a Vandermonde matrix, whence $\det\Phi$ has the product expansion $\prod_{0 \leq m < n < p} (\zeta^n - \zeta^m)$. Each factor $\zeta^n - \zeta^m$ is a positive real multiple of $\exp((m+n+\frac12)\pi i)$. It soon follows that $\det\Phi = i^{(1-p)/2} p^{p/2}$ (we already knew $\left|\det\Phi\right|$ because each eigenvalue has absolute value $\sqrt{p}$), and conclude as desired that $\tau = \sqrt{p}$ when $p \equiv 1 \bmod 4$ while $\tau = i\sqrt{p}$ when $p \equiv -1 \bmod 4$.

[This looks like a known but not very well-known argument that is easier to rediscover than to find in the literature. What is the original source?]

Answer by Noam D. Elkies for Hilbert's Nullstellensatz on polynomials with integer coefficients

2013-02-02T05:43:27Z

Yes. Given the degrees of the $g_i$, the equation $1 = \sum_i f_i g_i$ is tantamount to a system of linear equations in the coefficients of the $g_i$, and those linear equations have rational coefficients. Once such a system has a complex solution it automatically has a rational solution.

Answer by Noam D. Elkies for Examples of interesting false proofs

2013-01-15T18:00:37Z

Theorem. $\int_0^\infty \sin x \phantom. dx/x = \pi/2$.

Poof. For $x>0$ write $1/x = \int_0^\infty e^{-xt} \phantom. dt$, and deduce that $\int_0^\infty \sin x \phantom. dx/x$ is $$ \int_0^\infty \sin x \int_0^\infty e^{-xt} \phantom. dt \phantom. dx = \int_0^\infty \left( \int_0^\infty e^{-tx} \sin x \phantom. dx \right) \phantom. dt = \int_0^\infty \frac{dt}{t^2+1}, $$ which is the arctangent integral for $\pi/2$, QED.

The theorem is correct, and usually obtained as an application of contour integration, or of Fourier inversion ($\sin x / x$ is a multiple of the Fourier transform of the characteristic function of an interval). The poof, which is the first one I saw (given in a footnote in an introductory textbook on quantum physics), is not correct, because the integral does not converge absolutely. One can rescue it by writing $\int_0^M \sin x \phantom. dx/x$ as a double integral in the same way, obtaining $$ \int_0^M \sin x \frac{dx}{x} = \int_0^\infty \frac{dt}{t^2+1} - \int_0^\infty e^{-Mt} (\cos M + t \cdot \sin M) \frac{dt}{t^2+1} $$ and showing that the second integral approaches $0$ as $M \rightarrow \infty$; but this detour makes for a much less appealing alternative to the usual proof by complex or Fourier analysis.

Still the double-integral trick can be used legitimately to evaluate $\int_0^\infty \sin^m x \phantom. dx/x^n$ for integers $m,n$ such that the integral converges absolutely (that is, with $2 \leq n \leq m$; NB unlike the contour or Fourier approach this technique applies also when $m \not\equiv n \bmod 2$). Write $(n-1)!/x^n = \int_0^\infty t^{n-1} e^{-xt} \phantom. dt$ to obtain $$ \int_0^\infty \sin^m x \frac{dx}{x^n} = \frac1{(n-1)!} \int_0^\infty t^{n-1} \left( \int_0^\infty e^{-tx} \sin^m x \phantom. dx \right) \phantom. dt, $$ in which the inner integral is a rational function of $t$, and then the integral with respect to $t$ is elementary. For example, when $m=n=2$ we find $$ \int_0^\infty \sin^2 x \frac{dx}{x^2} = \int_0^\infty t \frac2{t^3+4t} dt = 2 \int_0^\infty \frac{dt}{t^2+4} = \frac\pi2. $$ As a bonus, we recover a correct proof of our starting theorem by integration by parts:

$$ \frac\pi2 = \int_0^\infty \sin^2 x \frac{dx}{x^2} = \int_0^\infty \sin^2 x \phantom. d(-1/x) = \int_0^\infty \frac1x d(\sin^2 x) = \int_0^\infty 2 \sin x \cos x \frac{dx}{x}; $$ since $2 \sin x \cos x = \sin 2x$, the desired $\int_0^\infty \sin x \phantom. dx/x = \pi/2$ follows by a linear change of variable.

Exercise Use this technique to prove that $\int_0^\infty \sin^3 x \phantom. dx/x^2 = \frac34 \log 3$, and more generally $$ \int_0^\infty \sin^3 x \frac{dx}{x^\nu} = \frac{3-3^{\nu-1}}{4} \cos \frac{\nu\pi}{2} \Gamma(1-\nu) $$ when the integral converges. [Both are in Gradshteyn and Ryzhik, page 449, formula 3.827; the $\nu=2$ case is 3.827#3, credited to D. Bierens de Haan, Nouvelles tables d'intégrales définies, Amsterdam 1867; the general case is 3.827#1, from Gröbner and Hofreiter's Integraltafel II, Springer: Vienna and Innsbruck 1958.]

Answer by Noam D. Elkies for Elementary applications of linear algebra over finite fields

2013-01-14T23:22:40Z

The game of Projective Set is tantamount to finding a linear dependence on $7$ (distinct, nonzero) vectors in $\mathbb{F}_2^6$. Linear algebra over $\mathbb{F}_2$ shows that there's always a solution, and moreover that the number of solutions is always $2^k-1$ for some positive integer $k$. How large can this $k$ get, and how many of the ${63 \choose 7} = 553270671$ possible deals attain this maximal $k$? [Thanks to Zach Abel for introducing me to this game.]

Answer by Noam D. Elkies for When is $n/\ln(n)$ close to an integer?

2012-12-24T19:57:13Z

[Edited mostly to extend the computation from $1.5 \cdot 10^{13}$ to a bit over $2^{50} > 10^{15}$ and give the heuristics for expected number of records for $\| r(n) \|$ vs. $\log n \cdot \| r(n) \|$]

Just ran across this. I see that Kevin's answer completely settles the original question, but meanwhile Will Jagy raised the question of finding new record lows for $$ \log n \cdot \left\| \frac{n}{\log n} \right\| $$ and proving their infinitude. I next outline a proof that there are infinitely many such record lows, and then report on a computation of all such $n$ up to $1.5 \cdot 10^{13}$.

For the infinitude: Since $r(n) := n / \log n$ can never be an exact integer, it is enough to prove that for each $\epsilon > 0$ there exist infinitely many solutions of $\| r(n) \| < \epsilon/\log n$. In fact it's not hard to show that $\| r(n) \|$ can get as small as some negative power of $n$, because $r(n)$ is almost linear (its second derivative is $o(n^{-1})$ as $n \rightarrow \infty$) and we can choose $n_0$ to make $r'(n_0)$ as far as possible from any rational number. If I did this right, we can find intervals $|n - n_0| \leq h$ in which $\min_n \| r(n) \| \ll h^{-1}$ where $h^{-1} = |r''(n_0)|^{1/3} \sim (n_0 \log^2 n_0)^{-1/3}$. For instance, we may choose $n_0$ so that $r'(n_0) = 1 / (k + \sqrt 2)$ for $k = 1, 2, 3, \ldots$ [that is, so that $\log n_0$ solves the quadratic equation $\lambda^2 = (k+\sqrt2) (\lambda-1)$]. On such an interval, $r(n)$ is approximated by $r(n_0) + r'(n_0)(n-n_0)$ to within $O(r''(n_0) (n-n_0)^2) = O(h^2/h^3) = O(h^{-1})$, and (since $h$ grows much faster than $k$) the arithmetic sequence with common difference $r'(n_0)$ is close enough to being equidistributed that it comes within $O(1/h)$ of an integer. [We probably expect that $\| r(n) \|$ is random enough that it gets as small as $c/n$ or even $o(1/n)$, but proving such a result must be well out of reach.]

For the numerical search, the problem is quite similar to MO.19170 on nearly-integral values of $\log_{10} n!$ (since $n/ \log n$, like $\log_{10} n!$, is nearly linear in $n$). Again it takes time only $\tilde O(N^{2/3})$ to find all examples with $n < N$ using a linear-approximation technique such as described at the bottom of page 15 of Lefèvre's slides. This is actually the same idea as in the previous paragraph: partition $[1,N]$ into intervals $|n-n_0| \leq h \sim (n_0 \log^2 n_0)^{1/3}$; in general $r'(n_0)$ might be so close to a rational number that equidistribution fails, but we can still use continued fractions to find all $n$ in that interval for which $\|r(n)\| \ll h^{-1}$.

I ran this with $N = 2^{50} > 10^{15}$ on ten alhambra heads. Most finished in under two days; two took an extra day or two, probably spending most of them on $n_0$ for which $r'(n_0)$ was nearly rational (in this case one can do much better than trying every $n \in [n_0-h,n_0+h]$ for which $\| r(n_0) + r'(n_0)(n-n_0) \|$ is small, but I didn't take the extra time to implement that refinement). The computation found fourteen new records beyond the 12 initial terms 2, 17, 163, 715533, 1432276, 6517719, 11523158, 11985596, 24102781, 254977309, 451207448, 1219588338 of OEIS sequence A178806, namely

2048539023, 10066616717, 42116139191, 47657002570, 73831354169, 122478947521, 143949453227, 3152420311977, 5624690531099, 14964977749017, 25999244327633, 92799025313425, 164330745650026, and 604329910739082.

There is also a new example, namely $n = 3040705645816$, of a number that is not in this sequence but does belong in the closely related OEIS sequence A178805, which consists of $n$ that achieve record low values of $\| r(n) \|$ instead of $\log n \cdot \| r(n) \|$. In general a $\log n \cdot \| r(n) \|$ record is automatically also an $\| r(n) \|$ record, but the converse can fail on occasion. If we imagine that the $\| r(n) \|$ are independent random numbers uniformly distributed on $(0,1/2)$ then the probability that $\| r(n) \|$ is a new record is $1/n$, so we expect $\log N + O(1)$ record values with $n \leq N$. The same question for $\log n \cdot \| r(n) \|$ is trickier, but if I did this right the probability that $\| r(n) \|$ is a new record but $\log n \cdot \| r(n) \|$ is not one is approximately $1 / n \log n$, so we expect only $\log\log N + O(1)$ examples such as $n = 3040705645816$ up to $N$, and might never see another one even though there should be infinitely many more.

Here is a table of the values of $n < 2^{50}$ for which $\| r(n) \|$ attains a new record low, together with the signed fractional part of $r(n)$, and $\log n$ times that fractional part: $$ \begin{array}{rrrc} 2 & -0.1146099 & -0.0794415 & \\ 5 & 0.1066747 & 0.1716863 & ! \\ 9 & 0.0960765 & 0.2111017 & ! \\ 13 & 0.0683262 & 0.1752532 & ! \\ 17 & 0.0002541 & 0.0007199 & \\ 163 & -1.26 \cdot 10^{-6} & -6.43 \cdot 10^{-6} & \\ 53453 & 1.22 \cdot 10^{-6} & 1.33 \cdot 10^{-5} & ! \\ 110673 & 6.68 \cdot 10^{-7} & 7.76 \cdot 10^{-6} & ! \\ 715533 & 3.84 \cdot 10^{-7} & 5.17 \cdot 10^{-6} & \\ 1432276 & 2.33 \cdot 10^{-7} & 3.30 \cdot 10^{-6} & \\ 6517719 & -2.00 \cdot 10^{-7} & -3.14 \cdot 10^{-6} & \\ 11523158 & -9.95 \cdot 10^{-8} & -1.62 \cdot 10^{-6} & \\ 11985596 & -7.26 \cdot 10^{-8} & -1.18 \cdot 10^{-6} & \\ 24102781 & 4.43 \cdot 10^{-9} & 7.53 \cdot 10^{-8} & \\ 254977309 & 9.12 \cdot 10^{-10} & 1.76 \cdot 10^{-8} & \\ 451207448 & 3.68 \cdot 10^{-10} & 7.33 \cdot 10^{-9} & \\ 1219588338 & -2.57 \cdot 10^{-10} & -5.38 \cdot 10^{-9} & \\ 2048539023 & -5.89 \cdot 10^{-11} & -1.26 \cdot 10^{-9} & \\ 10066616717 & 4.85 \cdot 10^{-11} & 1.12 \cdot 10^{-9} & \\ 42116139191 & -4.47 \cdot 10^{-11} & -1.09 \cdot 10^{-9} & \\ 47657002570 & -2.43 \cdot 10^{-11} & -5.97 \cdot 10^{-10} & \\ 73831354169 & 1.35 \cdot 10^{-11} & 3.38 \cdot 10^{-10} & \\ 122478947521 & 7.53 \cdot 10^{-13} & 1.92 \cdot 10^{-11} & \\ 143949453227 & -5.50 \cdot 10^{-13} & -1.41 \cdot 10^{-11} & \\ 3040705645816 & 5.18 \cdot 10^{-13} & 1.49 \cdot 10^{-11} & ! \\ 3152420311977 & -3.36 \cdot 10^{-13} & -9.67 \cdot 10^{-12} & \\ 5624690531099 & 1.28 \cdot 10^{-13} & 3.76 \cdot 10^{-12} & \\ 14964977749017 & -7.15 \cdot 10^{-14} & -2.17 \cdot 10^{-12} & \\ 25999244327633 & -2.02 \cdot 10^{-14} & -6.25 \cdot 10^{-13} & \\ 92799025313425 & 6.01 \cdot 10^{-15} & 1.93 \cdot 10^{-13} & \\ 164330745650026 & -1.00 \cdot 10^{-15} & -3.28 \cdot 10^{-14} & \\ 604329910739082 & -4.59 \cdot 10^{-16} & -2.27 \cdot 10^{-14} & \end{array} $$ the "!"'s mark the $\| r(n) \|$ records that aren't $\log n \cdot \| r(n) \|$ records.

Answer by Noam D. Elkies for Complex Zeroes of Stirling functions of the second kind

2013-01-04T18:20:45Z

Alexandre Eremenko already showed that for each $n>1$ the function $$ S_n(x) := \frac1{n!} \sum_{k=1}^n {n \choose k} (-1)^{n-k} k^x $$ has infinitely many zeros $x \in {\bf C}$. One can still say more: for each $n$ (including $n=2$, and for that matter $n=1$) the zeros are limited to a vertical strip $\sigma_0 < {\mathop{\rm Re}}(x) < \sigma_1$ (this is elementary: if the real part of $x$ is too positive or too negative then the $k=n$ or $k=1$ term dominates), and the number of complex conjugate pairs with $|{\mathop{\rm Im}}(x)| < T$ is asymptotic to $c_n T$ where $c_n := (2\pi)^{-1} \log n$.

The proof is similar to the standard proof of the asymptotic vertical distribution of zeros of the Riemann zeta function, but easier because $S_n$ is an elementary function. Use the argument principle to express the number of zeros in the rectangle $\sigma_0 < {\mathop{\rm Re}}(x) < \sigma_1$, $|{\mathop{\rm Im}}(x)| < T$ as a contour integral over its boundary. The integrals over the vertical $\sigma_0$ and $\sigma_1$ edges contribute $O_n(1)$ and $2 c_n T + O_n(1)$ respectively. For the horizontal edges: use the Hadamard factorization of $S_n$, take its logarithmic derivative, show that the number of zeros with $|{\mathop{\rm Im}}(x) - T| \leq 2$ is bounded, and show that the integral of $|S_n^{\phantom.\prime}/S_n|$ over the rectangle $[\sigma_0,\sigma_1] + i [T-1,T+1]$ is $O_n(1)$ and thus that we make the horizontal $S_n^{\phantom.\prime}/S_n$ integral also $O_n(1)$ by changing $T$ by at most $1$.

For $n=3$ one can be still more precise: for each $k=1,2,3,\ldots$, the horizontal strip $k c_3^{\phantom.} < {\mathop{\rm Im}}(x) < (k+1) c_3^{\phantom.}$ contains a zero $x_k$ of $S_3$, and the full set of zeros consists of these $x_k$, their complex conjugates, and the real zeros $x=1$ and $x=2$. This is obtained by applying Rouché's theorem to $6 S_3(x) = 3^x - 3\cdot 2^x + 3$ with comparison function $3^x + 3$. This $x_k$ can be approximated numerically by integrating $(2\pi i)^{-1} z (S_3^{\phantom.\prime}(z) / S_3(z)) dz$ around the boundary of this rectangle and then applying Newton's formula to get even closer. The first five complex zeros $x_1,x_2,x_3,x_4,x_5$ are approximately

 -0.3397375 +  8.9137244 i,
  2.8692517 + 15.2110263 i,
  0.0637801 + 18.6324632 i,
 -0.1248035 + 26.7730278 i, and
  2.9811739 + 31.1087024 i.

Note that ${\mathop{\rm Re}}(x_5)$ is almost $3$. It so happens that $\sigma_1$ is exactly $3$ (since $3^3 = 2 \cdot 2^3 + 3$). Of the $174$ zeros with $0 < {\mathop{\rm Im}}(x) < 1000$, the one with largest real part is $x_{116} \doteq 2.99976958 + 666.32539172i$. The least real part in that range is attained by $x_{158} \doteq -0.36455251 + 906.47874219i$ (while $\sigma_0 \doteq -0.3646005647$).

Answer by Noam D. Elkies for Are there Heronian triangles that can be decomposed into three smaller ones?

2013-01-02T03:10:24Z

Yes, for example the 13-14-15 triangle can be scaled by 11 to find a point $D$ at distance $80$, $91$, $102$ from the vertex opposite the side of length $11 \cdot 13$, $11 \cdot 14$, $11 \cdot 15$ respectively:

This was found by fixing $A,B,C$ and searching through the points $D$ of low height, using the parametrization of Pythagorean triples $x^2+y^2=d_1^2$ to search through only those $D$ that are already at rational distance from $(0,0)$, and then testing whether the distances to $B$ and $C$ are rational as well.

In fact, for any choice of triangle $ABC$, such points $D$ should be dense in the Euclidean plane, and thus in the interior of the triangle, because they're parametrized by a K3 surface with enough structure that standard tricks apply.

Let $A,B,C$ be the vertices of any rational Heronian triangle. We may choose Euclidean coordinates so that $A,B,C = (x_i,y_i)$ ($i=1,2,3$) with all $x_i$ and $y_i$ rational (for example, put $A$ at the origin and $B$ at $(x_2,0)$, etc.). Then the points $D=(x,y)$ at rational distances $d_i$ from $x_i$ correspond to solutions $(x,y,d_1,d_2,d_3)$ of the three Diophantine equations $(x-x_i)^2 + (y-y_i)^2 = d_i^2$ with each $d_i$ positive. Thus we seek rational points on the intersection $S$ of three quadrics in 5-space. Here the singularities of this intersection are mild enough that $S$ is birationally a K3 surface, as it would be if the intersection were smooth. The geometry yields several elliptic fibrations on $S$; e.g. for any line through (say) $A$ whose slope comes from a Pythagorean triangle, the points $D$ on that line that that are also at rational distance from $B$ and $C$ are parametrized by a genus-$1$ curve with rational points at infinity. Starting from those rational points (or those for which $D$ is the orthocenter, or indeed one of the vertices $A,B,C$), it should be straightforward to bounce around a few elliptic fibrations to find a dense set of rational points.

Answer by Noam D. Elkies for Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$

2012-12-15T02:14:01Z

There is no need to reinvent the wheel by estimating $\prod_{k<n}(1+\frac1{k^2})$ . The asymptotic formula for $f_n + i g_n$ follows readily from Stirling's approximation (as I already noted in my comment to the original question), and indeed the same is true for the asymptotics as $n \rightarrow \infty$ of $w \choose n$ for any $w \in {\bf C}$; the answer is simply $$ \phantom{*0000000000000000000} {w \choose n} = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) \frac{(-1)^n}{\Gamma(-w)} n^{-w-1} \phantom{0000000000000000000}(*) $$ (and the $O(1/n)$ can be refined to an asymptotic series in powers of $1/n$). Note that this gives zero precisely for the values $w=0,1,2,3,\ldots$ for which $-w$ is a pole of $\Gamma$, which are also the $w$ for which ${w \choose n} = 0$ for sufficiently large $n$. For $w=i$, we recover the observed behavior: $\Gamma(i)$ is a complex number of absolute value $(\pi / \sinh \pi)^{1/2}$ [in general $$|\Gamma(it)| = (\Gamma(it)\Gamma(-it))^{-1/2} = \left(\frac \pi {t \phantom. \sinh \pi t} \right)^{1/2} $$ for real $t \neq 0$], and $n^{-w-1}$ is a complex number of absolute value $1/n$ that goes once around the origin when $n$ increases by a factor $e^{2\pi}$. Thus each of $\lbrace f_n \rbrace$ and $\lbrace g_n \rbrace$ alternates in sign outside an infinite sequence of exceptions that's asymptotically a geometric sequence with common ratio $e^\pi$.

To prove (*), write $$ {w \choose n} = \frac{(-1)^n}{n!} \prod_{k=0}^{n-1} (k-w) = \frac{(-1)^n}{n!} \frac{\Gamma(n-w)}{\Gamma(-w)} = \frac{(-1)^n}{n\Gamma(-w)} \frac{\Gamma(n-w)}{\Gamma(n)}. $$ Now we understand $(-1)^n/n$, and the factor $1 / \Gamma(-w)$ is constant, so we're left with $\Gamma(n-w) / \Gamma(n)$. We apply the following form of Stirling's formula: there exists a constant $\varpi>0$ (known to equal $2\pi$, but we shall not need this) such that $$ \Gamma(z) = \bigl(1 + O(|z|^{-1}\bigr) z^z e^{-z} \sqrt{\varpi/z} $$ holds as $|z| \rightarrow \infty$ in the right half-plane, where $z^z = \exp (z \log z)$ and $\sqrt{\varpi/z}$ are defined using the principal branches of $\log z$ and $\sqrt z$. This gives $$ \frac{\Gamma(n-w)}{\Gamma(n)} = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) \frac{(n-w)^{n-w} e^{-(n-w)} (\varpi/(n-w))^{1/2}} {n^n e^{-n} (\varpi/n)^{1/2}} $$ $$ = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) \frac{(n-w)^{n-w}}{n^n} e^w \left(1-\frac{w}{n}\right)^{-1/2}. $$ Now the last factor is $1 + O(1/n)$; the factor $e^w$ is constant; and $$ (n-w)^{n-w} = (n-w)^{-w} (n-w)^n = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) n^{-w} (n-w)^n. $$ So we're left with $$ \frac{\Gamma(n-w)}{\Gamma(n)} = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) n^{-w} e^{-w} \left(1 - \frac{w}{n}\right)^n = \Bigl(1+O\bigl(\frac1n\bigr)\Bigr) n^{-w}. $$ This completes the proof of (*) (and the cancellation in the last step leads me to suspect that even this use of Stirling is more complicated than necessary).

Answer by Noam D. Elkies for Rational functions with a common iterate

2012-12-02T04:18:15Z

Over ${\bf C}$, An easy counterexample to question 3 is $f(x) = x^2$, $g(x) = cx^2$ where $c$ is a nontrivial cube root of unity. Then $f(f(x)) = g(g(x)) = x^4$ but $f$ and $g$ do not commute. There are similar examples for higher iterates.

[Added later] A more exotic construction yields further examples, some defined over ${\bf Q}$, such as the degree-4 pair $$ f(y) = \frac{y^4+18y^2-47}{8y^3}, \phantom{\infty} g(y) = \frac{f-3}{f+1} = \frac{y^4-24y^3+18y^2-27}{y^4+8y^3+18y^2-27} $$ with $f \circ f = g \circ g$ but $f \circ g \neq g \circ f$. This is a "Lattès map" associated to the elliptic curve $E: y^2 = x^3 + 1$: the function $f$ comes from the doubling map $P \mapsto 2P$, and $g$ comes from $P \mapsto 2P+T$ where $T$ is the 3-torsion point $(0,1)$ (as the $(f,g)=(x^2,cx^2)$ example does on the multiplicative group). This elliptic curve yields examples of $f \circ f = g \circ g$ and $f \circ g \neq g \circ f$ with any degree $m^2+mn+n^2$ as long as that's not a multiple of 3, with $f,g \in {\bf Q}(y)$ if $n=0$. Other elliptic curves with complex multiplication yield further examples using the $x$-coordinate rather than the $y$-coordinate, e.g. $f(x) = -x(x^4+6x^2-3)^2 / (3x^4-6x^2-1)^2$ and $g = (f-1)/(f+1)$ from tripling on $y^2=x^3-x$.

Answer by Noam D. Elkies for plane cubics and conic bundles

2012-11-30T06:05:39Z

Yes, at least if we're not in characteristic 2. Since all nodal cubics are projectively equivalent, it is enough to find one example. Trying a few symmetric $3 \times 3$ determinants soon turns up the matrix $$ M = \left[ \begin{array}{ccc} x & x & y \cr x & z & 0 \cr y & 0 & x \end{array} \right] $$ with determinant $x^2(z-x)-zy^2$. So the discriminant locus of the associated net of conics is $zy^2 = x^2(z-x)$, which has a node at $(x:y:z) = (0:0:1)$ [set $z=1$ to get the more familiar affine model $y^2 = x^2 - x^3$ with a node at the origin]. At that point $M$ becomes $$ \left[ \begin{array}{ccc} 0 & 0 & 0 \cr 0 & 1 & 0 \cr 0 & 0 & 0 \end{array} \right], $$ where the conic degenerates to a double line as desired.

Answer by Noam D. Elkies for Intersecting 4-sets

2012-11-06T14:45:50Z

The conjectured maximum of $N = \binom{\lfloor n/2\rfloor}{2}$ is correct except for $n=7$, when the maximum is $7$, and $8 \leq n \leq 11$, when the maximum is $14$. The maximal configuration is unique except for $n=12$, $13$, $15$, $16$, and $17$.

Let $L$ be the subgroup of ${\bf Z}^n$ generated by $(2{\bf Z})^n$ and the characteristic functions $e_i + e_j + e_k + e_l$ of each 4-set $\lbrace i,j,k,l \rbrace$ in our family $\cal F$ of subsets of $\lbrace 1,2,\ldots,n \rbrace$. Give $L$ the structure of lattice using the inner product $$ \langle x, y \rangle = \frac12 \sum_{i=1}^n x_i y_i $$ (i.e. half the usual inner product). Then $L$ is generated by vectors $2e_i$ and $e_i + e_j + e_k + e_l$ of norm $2$, any two of which are either orthogonal or have inner product $1$. Hence $L$ is an even integral lattice, with at least $2n+16|{\cal F}|$ roots (vectors of norm 2), namely $\pm 2 e_i$ and $\pm e_i \pm e_j \pm e_k \pm e_l$ for $\lbrace i,j,k,l \rbrace \in \cal F$. Equality holds iff $\cal F$ contains every tetrad $\lbrace i,j,k,l \rbrace$ such that $e_i + e_j + e_k + e_l \in L$.

Now we can use the theory of root systems to partition the set of roots of $L$ into mutually orthogonal simple root systems. Since $L$ contains the root lattice $A_1^n = (2{\bf Z})^n$, the only possible components of the root system of $L$ are $A_1$, $D_{2k}$ for $k \geq 2$, and the exceptional systems $E_7$ and $E_8$. These contribute respectively $0$, $\binom{k}{2}$, $7$ and $14$ tetrads to $\cal F$. Namely, each $A_1$ corresponds to a coordinate that does not appear in $\cal F$; each $D_{2k}$ corresponds to $k$ pairs of coordinates paired in each of $\binom{k}{2}$ possible ways; and $E_7$ and $E_8$ correspond to the tetrads of the Hamming $[7,3,4]$ and extended Hamming $[8,4,4]$ codes respectively.

It is now elementary bookkeeping to obtain the maximum configuration.

$\circ$ Except for $7 \leq n \leq 11$, the maximal $|{\cal F}|$ is $\binom{k}{2}$ for $n = 2k$ or $n = 2k+1$, attained by the $D_{2k}$ configuration.

$\circ$ For $n=7$, the maximum of $7$ is attained by the $E_7$ (Hamming) configuration, and for $8 \leq n \leq 11$, by $E_8 \oplus A_1^{n-8}$ (extended Hamming).

$\circ$ For $n=12$ ($n=13$), the maximum of $15$ is attained by both $D_{12}$ ($D_{12} \oplus A_1$) and $E_8 \oplus D_4$ ($E_8 \oplus D_4 \oplus A_1$).

$\circ$ For $n=15$, the maximum of $21$ is attained by both $D_{14} \oplus A_1$ and $E_8 \oplus E_7$.

$\circ$ Finally, for $n=16$ ($n=17$), the maximum of $28$ is attained by both $D_{16}$ ($D_{16} \oplus A_1$) and $E_8 \oplus E_8$ ($E_8 \oplus E_8 \oplus A_1$).

[The lattice $L$ corresponds via "construction A" to a binary linear code generated by $\cal F$, which is doubly even by hypothesis. Koch developed a theory of "tetrad systems" of such codes that could be used to give a more direct but less familiar derivation of this answer.]

Answer by Noam D. Elkies for The complete list of continued fractions like the Rogers-Ramanujan?

2012-10-06T03:53:02Z

[Edited again to give a second identity relating $E$ to eta products]

Continued fraction or not, an expression $q^{\frac{(r-s)^2}{8(r+s)}} f(\pm q^r, \pm q^s)$ is a modular form of weight $1/2$ for all integers $r,s$ with $r+s>0$, because it is a sum $\sum_{n=-\infty}^\infty \pm q^{(cn+d)^2}$ with rational $c,d$ and periodic signs. Therefore the quotient of two such expressions is a modular function, and takes algebraic valus at quadratic imaginary values.

The quotient $$ E(q) = q - q^2 + q^6 - q^7 + q^8 - q^9 + q^{11} - 2q^{12} + 2q^{13} - 2q^{14} + 2q^{15} \cdots $$ looks like a modular unit $-$ its logarithmic derivative has small coefficients $-$ but not quite an eta product; instead it seems to be a quotient of Klein forms: $$ E(q) = q \prod_{n=1}^\infty (1-q^n)^{\chi(n)}, $$ where $\chi$ is the Dirichlet character of conductor $12$, given by

$$ \chi(n) = \cases{ +1,& if $n \equiv \pm 1 \bmod 12$; \cr -1,& if $n \equiv \pm 5 \bmod 12$; \cr 0,& otherwise. } $$ Two identities relating $E$ to $\eta$ products, similar to but somewhat more complicated than the ones you give for $A,B,C,D,$ are $$ \frac1{E(q)} - E(q) = \frac{\eta(2\tau)^2 \eta(6\tau)^4}{\eta(\tau)\eta(3\tau)\eta(12\tau)^4}, $$ and (a bit simpler) $$ \frac1{E(q)} + E(q) = \frac{\eta(4\tau)}{\eta(\tau)} \Bigl(\frac{\eta(3\tau)}{\eta(12\tau)}\Bigr)^3. $$

Answer by Noam D. Elkies for The function $\sum_{0}^{\infty} x^n/n^n$

2012-10-08T21:34:15Z

[Edited to outline the end of the argument that $f(-M) \rightarrow 0$ (and to correct a few typos etc. while I'm at it)]

Yes, $F(x) \rightarrow 0$ from below as $x \rightarrow -\infty$. The convergence is slow, and precise asymptotic analysis seems to be somewhat annoying because it involves the lower branch of the Lambert W function.

The massive cancellations in $\sum_{n=0}^\infty x^n/n^n$ for $x \rightarrow -\infty$ can be tamed by the familiar device of writing $$ \frac1{n^n} = \frac1{(n-1)!} \int_0^\infty t^{n-1} e^{-nt} dt $$ for $n=1,2,3,\ldots$. Multiplying by $x^n$, summing over $n>0$, and restoring the $n=0$ term $x^0/$"$0^0$"$=1$ yields $$ f(x) = 1 + x \int_0^\infty e^{txe^{-t}} e^{-t} dt. $$ Hence if $x=-M$ then $$ f(x) = f(-M) = 1 - M \int_0^\infty e^{-Mte^{-t}} e^{-t} dt, $$ and as $M \rightarrow +\infty$ the integral naturally splits into the parts $t \leq 1$ where $t e^{-t}$ is increasing and $t \geq 1$ where $t e^{-t}$ is decreasing. We let $u = t e^{-t}$, so the integrand becomes $e^{-Mu} du/(1-t)$. For $t<1$ we use Abel's power series $t = \sum_{m=1}^\infty m^{m-1} u^m/m!$ to expand the integral in an asymptotic series: $$ \int_0^1 e^{-Mte^{-t}} e^{-t} dt \sim \frac1M + \frac1{M^2} + \frac{2^2}{M^3} + \frac{3^3}{M^4} + \frac{4^4}{M^5} + \cdots $$ which is already enough to get $f(-M) < 0$ for large $M$. [Curiously the asymptotics of $\sum_{n=0}^\infty (-M)^n/n^n$ have led us to the divergent series $\sum_{n=1}^\infty n^n/M^n$.]

But the resulting bound $f(-M) < -1/M$ underestimates $|f(-M)|$: numerically $f(-100) \simeq -.1826$, $\phantom.$ $f(-1000) \simeq -.1180$, and $\phantom.$ $f(-10000) \simeq -.0899$, suggesting that $f(-M)$ decays only as $-1/\log M$ or so. The reason must be the $t>1$ part of the integral. On this part, $t = \log(1/u) + \log\log(1/u) + o(1)$ as $t \rightarrow \infty$, so the integral behaves to first order like $\int_0^{1/e} e^{-Mu} du / \log(1/u)$. Now $\log(1/u) \rightarrow 0$ as $u \rightarrow 0+$, but the convergence is slower than any positive power of $u$. Therefore, the integral is $o(1/M)$, which completes the argument that $f(x) \rightarrow 0$ as $x \rightarrow -\infty$; but the integral is not $O(1/M^\theta)$ for any $\theta > 1$, so $f(-M)$ decays slower than any positive power of $M$.

A more thorough asymptotic analysis of the $t>1$ integral as $M \rightarrow \infty$ looks routine but unpleasant, so I'll stop at this point; perhaps somebody else here will be interested in pursuing it further.

Answer by Noam D. Elkies for There exists B subset A, |B| = log n, A \cap 2*B = \emptyset

2012-09-15T18:33:18Z

[Edited to give more information in reply to Terry Tao's comment and Seva's query]

I told Zach Abel of this problem, and the next day he e-mailed me that Zach and Andrey Grinsphun (both are graduate students at MIT) obtained the following solution:

incrementally take the largest element that doesn't violate the condition. Each insertion at most doubles the number of elements of $A$ that are ruled out, so it gets $\Omega(\log n)$ elements.

In later correspodence Andrey explains that the "ruled out" elements include those of $B$ itself, and it's actually not "doubles" but "doubles and adds 1 to", so after choosing $m$ elements there are at most $2^m-1$ forbidden. In more detail (translating some English into equivalent formulas):

List $A$ in increasing order $A=\lbrace a_1,...,a_n \rbrace$. Start with $B$ empty and note that this forbids at most $2^m-1=0$ elements ($m=|B|$, the size of $B$).

Then if we currently have some $B$ of size $m$, when we choose the largest element that is not forbidden, since $B$ forbids at most $2^m-1$ elements by induction we may add $a_k$ to $B$ for some $k \geq n-2^m+1$. Then the number of new forbidden elements is at most $1+|(A-a_k) \cap A|$ (the $1$ comes from $a_k$ itself). But $|(A-a_k) \cap A| \leq |\lbrace x\in A : x > a_k \rbrace|$, which is at most the number of elements $B$ forbids. In particular, it's at most $2^m-1$, so the number of new forbidden elements is at most $2^m-1+1=2^m$, and so the total number of forbidden elements is at most $2^m+2^m-1 = 2^{m+1}-1$.

[CW because this is not my own argument. I still wonder if $\log n$ is anywhere near the right order; it feels surprisingly small. It's not even obvious to me that there are sets $A$ for which the smallest $B$ has size $o(n)$, let alone $n^{o(1)}$. (See Terry Tao's reply: Ruzsa indeed obtained an $n^{o(1)}$ bound!)]

Answer by Noam D. Elkies for A 14th and 26th-power Dedekind eta function identity?

2012-09-17T04:11:58Z

This question asks in effect to show that $\eta^n$ is a $\pm p^{n/2}$ eigenfunction for the Hecke operator $T_p$. The claim holds because each of these $\eta^n$ happens to be a CM form of weight $n/2$, and $p$ is inert in the CM field ${\bf Q}(i)$ or ${\bf Q}(\sqrt{-3})$. In plainer language, the sum over $k$ takes the $q$-expandion $$ \eta(\tau)^n = \sum_{m \equiv n/24 \phantom.\bmod 1} a_m q^m $$ and picks out the terms with $p|m$, multiplying each of them by $p$; and the result is predictable because the only $m$ that occur are of the form $(a^2+b^2)/d$ or $(a^2+ab+b^2)/d$ where $d = 24 / \gcd(n,24)$, and the congruence on $p$ implies that $p|m$ if and only if $p|a$ and $p|b$.

For $n=2$ this is immediate from the pentagonal number identity, which states in effect that $\eta(\tau)$ is the sum of $\pm q^{c^2/24}$ over integers $c \equiv 1 \bmod 6$, with the sign depending on $c \bmod 12$ (and $q = e^{2\pi i \tau}$ as usual). Thus $$ \eta^2 = \sum_{c_1^{\phantom0},c_2^{\phantom0}} \pm q^{(c_1^2+c_2^2)/24} = \sum_{a,b} \pm q^{(a^2+b^2)/12} $$ where $c,c' = a \pm b$.

Once $n>2$ there's a new wrinkle: the coefficient of each term $q^{(a^2+b^2)/d}$ or $q^{(a^2+ab+b^2)/d}$ is not just $\pm 1$ but a certain homogeneous polynomial of degree $(n-2)/2$ in $a$ and $b$ (a harmonic polynomial with respect to the quadratic form $a^2+b^2$ or $a^2+ab+b^2$). Explicitly, we may obtain the CM forms $\eta^n$ as follows:

@ For $n=4$, sum $\frac12 (a+2b) q^{(a^2+ab+b^2)/6}$ over all $a,b$ such that $a$ is odd and $a-b \equiv1 \bmod 3$. [This is closely related with the fact that $\eta(6\tau)^4$ is the modular form of level $36$ associated to the CM elliptic curve $Y^2 = X^3 + 1$, which happens to be isomorphic with the modular curve $X_0(36)$.]

@ For $n=6$, sum $(a^2-b^2) q^{(a^2+b^2)/4}$ over all $a \equiv 1 \bmod 4$ and $b \equiv 0 \bmod 2$.

@ For $n=8$, sum $\frac12 (a-b)(2a+b)(a+2b) q^{(a^2+ab+b^2)/3}$ over all $(a,b)$ congruent to $(1,0) \bmod 3$.

@ For $n=10$, sum $ab(a^2-b^2) q^{(a^2+b^2)/12}$ over all $(a,b)$ congruent to $(2,1) \bmod 6$.

@ Finally, for $n=14$, sum $\frac1{120} ab(a+b)(a-b)(a+2b)(2a+b)q^{(a^2+ab+b^2)/12}$ over all $a,b$ such that $a \equiv 1 \bmod 4$ and $a-b \equiv 4 \bmod 12$.

I can't give a reference for these identities, but once such a formula has been surmised it can be verified by showing that the sum over $a,b$ gives a modular form of weight $n/2$ and checking that it agrees with $\eta^n$ to enough terms that it must be the same.

Answer by Noam D. Elkies for Parity dependent population inversion in Mordell elliptic curves

2012-09-03T03:15:57Z

The parity of the analytic rank of any elliptic curve $E_k: y^2 = x^3 + k$ over ${\bf Q}$ was determined in the paper

Liverance, Eric: A formula for the root number of a family of elliptic curves. J. Number Theory 51 #2, 288--305 (1995).

(This reference was posted a few weeks ago by Larry Washington to the NMBRTHRY mailing list in response to another question on the parity of some curves $E_k$.)

Suppose $k$ is a sixth-power-free integer, and write $k = 2^b 3^c k_1$ with $\gcd(k_1,6) = 1$. Then Liverance writes the sign of the functional equation of $E_k$ as $-w^{\phantom.}_2 w^{\phantom.}_3 (-1)^r$, where:

$w^{\phantom.}_2 = 1$ or $-1$ depending only on $b$ and on $3^c k_1 \bmod 4$;

$w^{\phantom.}_3 = 1$ or $-1$ depending only on $c$ and on $2^b k_1 \bmod 9$;

and $r$ is the number (without multiplicity) of prime factors of $k_1$ congruent to $-1 \bmod 6$.

[NB Liverance's $w^{\phantom.}_2$ and $w^{\phantom.}_3$ are not quite the same as the local root numbers of $E_k$ at $2$ and $3$, though they are closely related with these root numbers.]

Therefore: if $k$ is not divisible by the square of any prime congruent to $-1 \bmod 6$, then the parity is determined entirely by $w^{\phantom.}_2$, $w^{\phantom.}_3$, and whether $k>0$ or $k<0$. This happens in particular if $k$ has no $-1 \bmod 6$ factors at all, which is the case for the quadratic polynomials $k = -108 t^2 + 36 t - 7$ and $k = -108 t^2 + 36 t - 67$ in K.Acres' self-answer, because their discriminants are of the form $-3d^2$. Moreover, for each of these polynomials $k \bmod 36$ is constant with $\gcd(k,6) = 1$, so the sign of the functional equation is the same for all $t$. The smaller examples $-6t^2-8$ and $6t^2+2$ from K.Acres' comment also have discriminants $-3d^2$, but showing that their sign is constant requires some case analysis for the variation of $b$, $c$, and $k_1$ with $t$.

Even when the sign is not fully predictable there can be large biases. For example, in the arithmetic progression $k=36n+1$ the sign is usually $+1$ if $k>0$ and $-1$ if $k<0$. There are exceptions (starting at $k=36\cdot8+1 = 17^2$ and $k=36\cdot9+1 = 5^2 13$), but they require that $k$ be divisible by $p^2$ for some $p \equiv -1 \bmod 6$, and that happens less than 6% of the time.

Answer by Noam D. Elkies for Real intersections of plane cubic curves

2012-08-28T18:01:25Z

[Revised because I read too quickly and thought the problem was to find two connected cubics meeting in nine points]

Here's a version of the construction with two sets of three lines that may be easier to parse visually:

Each triplet of lines forms an equilateral triangle; these are plots of $C=40c$ and $C=240c$ where $$ C = (y-3) (y+6-3^{1/2}x) (y+6+3^{1/2}x), $$ $$ c = (x+1) (x-2-3^{1/2}y) (x-2+3^{1/2}y). $$

Answer by Noam D. Elkies for Hexagonal rooks

2012-07-31T03:22:19Z

Nice question!

For the maximum number of pairwise non-defending rooks, Will Sawin proved an upper bound of $(2n/3) + 1$ in his comment to the original question. This bound is attained, at least to within $O(1)$, by two rows of $n/3 - O(1)$ rooks each, starting from around $(2n/3,n/3,0)$ and $(n/3,2n/3,1)$ and proceeding by steps of $(-1,-1,2)$ until reaching the $y=0$ or $x=0$ edge of the triangle. This construction generalizes Sawin's five-Rook placement for $n=6$.

On further thought, it seems we actually achieve $\lfloor (2n/3) + 1 \rfloor$ exactly for all $n$. Here's how it works for $n=12$ and $n=15$, with $(2n/3)+1 = 9$ and $11$ respectively:

                                            .   
                                           . . 
                                          . . . 
            .                            . . . . 
           . .                          . . . . . 
          . . .                        R . . . . . 
         . . . .                      . . . . . . R 
        R . . . .                    . R . . . . . . 
       . . . . . R                  . . . . . . . R . 
      . R . . . . .                . . R . . . . . . . 
     . . . . . . R .              . . . . . . . . R . . 
    . . R . . . . . .            . . . R . . . . . . . . 
   . . . . . . . R . .          . . . . . . . . . R . . . 
  . . . R . . . . . . .        . . . . R . . . . . . . . . 
 . . . . . . . . R . . .      . . . . . . . . . . R . . . . 
. . . . R . . . . . . . .    . . . . . R . . . . . . . . . .

Starting from such a solution with $n=3m$, we can add an empty row to get an optimal solution for $n=3m+1$, and remove an edge (and the Rook it contains) to get an optimal solution for $n=3m-1$. So this should solve the problem for all $n$.

Jeremy Martin also asks:

More generally, is anything known about the graph whose vertices are these ordered triples and whose edges are rook moves?

I don't remember reading about this graph before. Experimentally (for $3 \leq n \leq 16$) its adjacency matrix has all eigenvalues integral, the smallest being $-3$ with huge multiplicity $n-1\choose 2$; more precisely:

Conjecture. For $n \geq 3$ the eigenvalues of the adjacency matrix are: a simple eigenvalue at the graph degree $2n$; a $n-1\choose 2$-fold eigenvalue at $-3$; and a triple eigenvalue at each integer $\lambda \in [-2,n-2]$, except that $\mu := \lfloor n/2 \rfloor - 2$ is omitted, and $\mu - (-1)^n$ has multiplicity only $2$.

This is probably not too hard to show. For example, the $\lambda = -3$ eigenvectors constitute the codimension-$3n$ space of functions whose sum over each of the $3(n+1)$ Rook lines vanishes. [Added later: in the comment Jeremy Martin reports that he and Jennifer Wagner already made and proved the same conjecture.]

Given that the minimal eigenvalue is $-3$, it follows by a standard argument in "spectral graph theory" that the maximal cocliques have size at most $3(n+1)(n+2)/(4n+6) = 3n/4 + O(1)$. But that's asymptotically worse than $2n/3 + O(1)$, though it's still good enough to prove the optimality of Will Sawin's cocliques of size $5$ for $n=6$ and of size $7$ for $n=9$.

Here's some gp code to play with this graph and its spectrum:

{
R(n)=
  l = [];
  for(a=0,n,for(b=0,n-a,l=concat(l,[[a,b,n-a-b]])));
  matrix(#l,#l,i,j,vecmin(abs(l[i]-l[j]))==0) - 1
}

running "R($n$)" puts a list of the vertices in "l" and returns the adjacency matrix with the corresponding labeling. So for instance

matkerint(R(7)-2)~
matkerint(R(8)-1)~

returns matrices whose rows are nice generators of the $2$-dimensional eigenspaces of the $n=7$ and $n=8$ graphs.

Comment by Noam D. Elkies

2013-05-21T18:53:20Z

The canonical answer is Sturm sequences (see for example the Wikipedia entry en.wikipedia.org/wiki/Sturm%27s_theorem ), which let one count the roots of a polynomial of any degree in ${\bf R}$ or in an interval. I might have written more about it, but the question was already closed so this will have to do.

Comment by Noam D. Elkies

2013-05-19T19:01:17Z

Is this really a formula for $h^-(p)$, not $\log h^-(p)$?

Comment by Noam D. Elkies

2013-05-19T01:17:07Z

The OP must want it to be Lipschitz with respect to the metric induced from the Euclidean plane, not the intrinsic Riemannian metric on the ellipse and circle. It still feels like the answer should still be yes but it's not as immediate.

Comment by Noam D. Elkies

2013-05-19T00:29:39Z

I always assumed it was because they correspond to affine reflection groups in the way that finite-dimensional semisimple algebras correspond to spherical (Euclidean) reflection groups.

Comment by Noam D. Elkies

2013-05-17T17:11:32Z

This seems more suitable for artofproblemsolving, but anyway: Since the polynomial is linear in each variable $y_i$ separately (once $N>2$), we may assume each $y_i \in \lbrace 0, 1 \rbrace$ (even if the intention was to just limit to the hypercube $0 \leq y_i \leq 1$. So we're just asking for the maximal number of 010 patterns in a cycle of $N+1$ zeros and ones. Since no two consecutive triples can be 010, the count is at most $\lfloor (N+1)/2 \rfloor$, and this is easily attained, and only by 010101... and its cyclic shifts (a total of $2$ if $N$ is even and $N+1$ if $N$ is odd).

Comment by Noam D. Elkies

2013-05-17T16:16:29Z

Actually I'm not using anything lke that (certainly not for an arbitrary field). Another way to say this is to choose projective coordinates so $A$, $B$, and $C$ are at the unit vectors $(1:0:0)$, $(0:1:0)$, and $(0:0:1)$, and then scale those coordinates so that $O$, which must have all three coordinates nonzero (else it's on one of the lines $AB$, $AC$, $BC$) is on $(1:1:1)$; then $OA$ is the line $y=z$, so $A'=OA \cap BC$ is $(0:1:1)$, and likewise $B = (1:0:1)$ and $C = (0:1:1)$. Now calculate that the determinant of $A,B,C$ is $2$, so $ABC$ are collinear iff we're in characteristic 2.

Comment by Noam D. Elkies

2013-05-15T03:00:31Z

...and conversely, if $k$ does have characteristic $2$ then $A',B',C'$ are always collinear...

Comment by Noam D. Elkies

2013-05-15T02:59:49Z

Yes, a line drawing is impossible, over ${\bf R}$ or any field $k$ not of characteristic $2$. Let $A,B,C,O$ be non-collinear points of the Fano plane, and $A',B',C'$ the intersections of $AO,BO,CO$ with $BC,CA,AB$ respectively. By Ceva's theorem (actually proved by Al-Mutaman centuries earlier, and extended algebraically to the case where $O$ is outside the triangle, and indeed to arbitrary $k$), points $A',B',C'$ divide segments $BC,CA,AB$ in signed ratios whose product is $1$. But by Menealus' theorem, $A',B',C'$ are collinear iff that product is $-1$. Since $1 \neq -1$ we're done.

Comment by Noam D. Elkies

2013-05-10T19:59:16Z

Actually you only get every other derivative for free this way. The functional equation says $\xi(s) = \pi^{s/2} \Gamma(s/2) \zeta(s)$ is symmetric about $s = 1/2$, so its odd-order derivatives vanish there, which gives linear equations on the $\zeta^{(n)}(1/2)$ that let you solve for $\zeta^{(2m+1)}(1/2)$ as a linear combination of $\zeta(1/2)$, $\zeta''(1/2)$, $\zeta^{(4)}(1/2)$, ..., $\zeta^{(2m)}(1/2)$. But you still can't solve for the even-order derivatives in terms of derivatives of lower order.

Comment by Noam D. Elkies

2013-05-09T22:06:03Z

Then too, some numerically evident propositions are false... For example, $$ \sum_{n=1}^\infty \frac{(3n-2)!}{(2n)!} \frac{(2n+99)!}{(3n+99)!} $$ is not quite equal to what numerical computation suggests. See math.harvard.edu/~elkies/Misc/sol11.html .

Comment by Noam D. Elkies

2013-05-09T04:18:51Z

But the last puzzle was already solved by Fermat... $$ $$ ...Which also suggests an alternative approach to the equation $a^2+b^2=c^2+d^2$ starting from the factorization $(a+bi)(a-bi)=(c+di)(c-di)$ in ${\bf Z}[i]$.

Comment by Noam D. Elkies

2013-05-09T02:13:40Z

$a^2+b^2=c^2+d^2 \Longleftrightarrow a^2-c^2=d^2-b^2 \Longleftrightarrow (a-c)(a+c)=(d-b)(d+b)$. Now the primitive solutions of $rs=tu$ are exactly $(r,s,t,u) = (xx',yy',xy',x'y)$ with $\gcd(x,y)=\gcd(x',y')=1$ (and some positivity condition to avoid duplication with factors of $-1$). If $(a,b,c,d)$ is primitive then $(r,s,t,u)$ is primitive up to a factor of $2$ and satisfies $r\equiv s$ and $t\equiv u \bmod 2$. So just figure out what to do with $x,x',y,y' \bmod 2$ and you're done.

Comment by Noam D. Elkies

2013-05-07T06:13:45Z

Yes, JHI, as I wrote correctly in my actual answer; here I must have been distracted by the alphabetical progression $-$ sorry. Unlike answers, comments cannot be edited here except by deleting the original comment and entering the corrected text for a new comment...

Comment by Noam D. Elkies

2013-05-06T23:44:39Z

Thanks too for accept ing my new answer. This curiously gives GHI the rare, perhaps unique, distinction of earning a gold Populist badge for his first and only MO answer! Populist or not, GHI's answer is necessary to show that the 8-piece dissection is minimal, and greatly helped focus my search using the key condition that each piece much include a corner of the $6 \times 6 \times 6$ cube. It also has the virtue of applying to all $(a,b,c;d)$, not just $(3,4,5;6)$. $$ $$ While I'm at it: who is "GHI"? When citing his contribution I'd like to credit a real person rather than a pseudonym.

Comment by Noam D. Elkies

2013-05-06T20:30:53Z

Thanks! The 2-D illustration was possible because it's how I was able to find the dissection in the first place $-$ fortunately no coordinate permutation was needed except for boxes. It would have been much harder both to find and to illustrate the dissection if some of the pieces were as complicated as in the 9-piece dissection that you mentioned and F.Brunault posted.