Zagier Problems

Three problems were posed by Don Zagier after each of his five lectures at the Colloquium. You can see the problems below and click on the link for the answer to each one.

If you want a more readable copy of the problems or solutions, they are available as:

Problems : AMS Tex file or dvi file or postscript file

Solutions: AMS Tex file or dvi file or postscript file
First Day: Number Theory
  1. Somebody incorrectly remembered Fermat's little theorem as saying that the congruence an+1=a(modn)a^{n+1} = a (mod n) holds for all aa if nn is prime. Describe the set of integers nn for which this property is in fact true.

  2. Prove or disprove: for every odd number kk there is a prime of the form 2nk+12^{n}k + 1.

  3. Show that if (a2+b2)/(ab+1)(a^{2} + b^{2})/(ab + 1) (for a,bNa, b \isin \mathbb{N}) is integral, then it is a perfect square.

Second Day: Algebra
  1. Show that there is no ring (= commutative, with 1) with exactly five units.

  2. Show that if a group has only finitely many elements of finite order, then these form a subgroup.

  3. Let PP and SS denote the direct product and direct sum of countably many copies of Z\mathbb{Z}, respectively, i.e. PP is the set of all sequences of integers (a1,a2,a3,...)(a_{1}, a_{2}, a_{3}, ... ) with the abelian group structure given by componentwise addition, and SS is the subgroup consisting of all sequences with ai=0a_{i} = 0 for ii sufficiently large. Show that HomZ(P,Z)_{\mathbb{Z}}(P, \mathbb{Z}) is isomorphic to SS.

Third Day: Polynomials
  1. Associate to a prime the polynomial whose coefficients are the decimal digits of the prime (e.g. 9x3+4x2+39 x^{3} + 4 x^{2} + 3 for the prime 9403). Show that this polynomial is always irreducible.

  2. Suppose that bnxn+bn1xn1+...+b1x+b0b_{n} x^{n} + b_{n-1} x^{n-1} + ... + b_{1}x + b_{0} in R[x]\mathbb{R}[x] has only real roots. Show that the polynomial bn/n!xn+bn1/(n1)!xn1+...+b1/1!x+b0b_{n}/n! x^{n} + b_{n-1}/(n-1)! x^{n-1} + ... + b_{1}/1! x + b_{0}, has the same property.

  3. Let p=2m1p = 2m - 1 be an odd prime. Show that the polynomial (1x)m+1+xm(1 - x)^{m} + 1 + x^{m} is twice a square in Fp[x]F_{p}[x].

Fourth Day: Geometry
  1. Let AA and BB be two adjacent vertices of an equilateral polygon. If the angles at all other vertices are known to be rational (when measured in degrees), show that the angles at AA and BB are also rational. Give a counterexample to this statement when AA and BB are not assumed to be adjacent.

  2. A rectangle RR is the union of finitely many smaller rectangles (non-overlapping except on their boundaries), each one of which has at least one rational side. Show that RR has the same property.

  3. Mark an angle a(0<a<2π)a (0 < a < 2π) on a pie-plate, and pick another angle b(0<b<2π)b (0 < b < 2π).
    Define an operation on the pie as follows:
    Cut out the slice of pie over the marked angle, lift it up, turn it over, replace it, and rotate the whole pie on the plate by the angle bb. Show that, whatever the values of aa and bb, this operation has finite order (i.e., after a finite number of iterations every piece of the pie is in its original position).

Fifth Day: Sequences and recursions
  1. Define a sequence t1,t2,t3,...t_{1}, t_{2}, t_{3}, ... by the recursion
    tn+5=(tn+4tn+1+tn+3tn+2)/tnt_{n+5} = (t_{n+4} t_{n+1} + t_{n+3} t_{n+2} )/t_{n}
    with initial values (1, 1, 1, 1, 1). Prove the statement that all of the tnt_{n} are integral.

  2. Define a sequence u1,u2,u3,...u_{1}, u_{2}, u_{3}, ... by the formula

    Show that the statement "none of the unu_{n} are integral" is false, but that the first counterexample is approximately 102019025 .

  3. Define a sequence v1,v2,v3,...v_{1}, v_{2}, v_{3}, ... by the recursion
    vn=(2+v12+...+vn12)/nv_{n} = (2 + v_{1}^{2} + ... + v_{n-1}^{2}) / n.
    Show that the statement "all of the vnv_{n} are integral" is false, but that the first counterexample is approximately 10178485291567 .

Supplementary problem

During the conference, a further problem was posed by one of the participants, namely, to prove that in any covering of a square checkerboard (of necessarily even edge length) by 2 × 1 dominos, there would always be a horizontal or vertical line through the checkerboard not passing through any domino.
During the ensuing discussion, a generalisation was conjectured by another participant (viz., me), namely, that the same is true for any rectangular checkerboard.
Since I know that I was not the only person who tried to prove these assertions, it may be worth communicating that both are in fact wrong, counterexamples of smallest size for the generalisation and for the original assertion being the 5 × 6 and 8 × 8 checkerboards:

    1 2 3 3 1 1              1 1 2 1 1 2 2 3
    1 2 1 2 2 3              2 3 2 3 3 4 1 3
    3 3 1 3 1 3     and      2 3 1 1 2 4 1 2  ,    respectively.
    4 2 2 3 1 2              1 4 4 3 2 3 3 2
    4 1 1 4 4 2              1 3 1 3 1 1 4 1
                             2 3 1 2 4 3 2 2
                             2 4 4 2 4 3 4 1
                             1 1 3 3 1 1 4 1

If you have any comments, you can mail me.
Don Zagier 1996