Comments on Earlier Problems

76:60 (Peter Weinberger) Let |f| denote the number of non-zero coefficients of a polynomial f. Is there a function A such that |(f, g)| ≤ A(|f|, |g|)? Can such an A be a polynomial? The example f = (x^{ab} + 1)(x^{b} + 1)/(x + 1), g = (x^{ab} + 1)(x^{b} + 1)/(x^{a} + 1) with a > b − 1, a even, b odd shows that if such an A exists then A(n, n) ≫ n^{2}.

Solution: Andrzej Schinzel writes that the answer to this problem is negative, and a simple counterexample is f = x^{ab} − 1, g = (x^{a} − 1)(x^{b} − 1), where |f| = 2, |g| = 4 and |(f, g)| can be arbitrarily large. The only difficult case in characteristic 0 is |f| = |g| = 3.

86:05 (Michael Filaseta) Is f_{n}(x) = \frac{d}{dx}(x^{n} + x^{n−1} + ⋯ + x + 1) irreducible for all positive integers n? For almost all n?

Solution: The “almost all” question is answered in the affirmative in

A. Borisov, M. Filaseta, T. Y. Lam, O. Trifonov, Classes of polynomials having only one non-cyclotomic irreducible factor, Acta Arith. 90 (1999) 121–153,

where Theorem 1 states that “if ϵ > 0 then for all but O(t^{1/3+ϵ}) positive integers n ≤ t the derivative of the polynomial f(x) = 1 + x + x^{2} + ⋯ + x^{n} is irreducible.”

88:06 (Emil Grosswald) Mike Filaseta proved that almost all Bessel polynomials [polynomial solutions of x^{2}y′′ + xy′ − n(n + 1)y = 0 with y(0) = 1] are irreducible over Q. Get rid of “almost all”.

Solution: In work submitted for publication, Filaseta and Trifonov write the Bessel polynomials as

y_{n}(x) = ∑_{j=0}^{n} \frac{(n + j)!}{2^{j}(n − j)!j!}x^{j}

and prove that if n is a positive integer and a_{0}, a_{1}, …, a_{n} are arbitrary integers with |a_{0}| = |a_{n}| = 1 then

∑_{j=0}^{n} a_{j} \frac{(n + j)!}{2^{j}(n − j)!j!}x^{j}

is irreducible.

The techniques are similar to those used in

M. Filaseta, The irreducibility of all but finitely many Bessel polynomials, Acta Math. 174 (1995) 383–397.

93:20 (Eugene Gutkin via Jeff Lagarias) [...] consider the polynomials

p_{n}(x) = \frac{(n − 1)(x^{n+1} − 1) − (n + 1)(x^{n} − x)}{(x − 1)^{3}}

[which arise in the solution of tan nθ = n tan θ] for n ≥ 1.

Conjecture. p_{n}(x) is irreducible if n is even, and is x + 1 times an irreducible if n is odd.

Solution: This is true for almost all n. Theorem 4 of the four-author paper cited above states that if ϵ > 0 then for all but O(t^{4/5+ϵ}) positive integers n ≤ t the polynomial p(x) = (n − 1)(x^{n+1} − 1) − (n + 1)(x^{n} − x) is (x − 1)^{3} times an irreducible polynomial if n is even and (x − 1)^{3}(x + 1) times an irreducible polynomial if n is odd.

95:18 (Martin LaBar, via Richard Guy) Is there a 3×3 magic square with distinct square entries?

Remark: Comments on this problem have appeared in each problem set since it was first proposed.

Andrew Bremner, On squares of squares, Acta Arith. 88 (1999) 289–297

constructs parametrized families of 3 × 3 matrices with distinct square entries and with all sums equal except that along the non-principal diagonal.

97:22 (John Selfridge) Let n = rs^{2}, r square-free, r > 1. It is conjectured that for all such n except n = 8 and n = 392 there exist integers a, b with n < a < b < r(s + 1)^{2} such that nab is a square.

Remark: See the paper,

Paul Erdős, Janice L. Malouf, J. L. Selfridge, Esther Szekeres, Subsets of an interval whose product is a power, Discrete Math. 200 (1999) 137–147.

Selfridge reports that he and Aaron Meyerowitz have proved that if there is a counterexample n > 392 then n is at least on the order of 10^{30000}.

Problems Proposed 16 & 19 Dec 99

99:01 (John Wolfskill) Let d ≡ 3 (mod 4) be positive and squarefree. Let a fundamental unit in Z[\sqrt{d}] be given by ϵ = a+b\sqrt{d} > 1. Characterize those d for which \sqrt{2} is in Q(\sqrt{ϵ}).

Remarks: \sqrt{2} is in Q(\sqrt{ϵ}) for all prime d and for some but not all composite d.

Gary Walsh shows that the following are equivalent:

a) \sqrt{2} is in Q(\sqrt{ϵ});

b) at least one of the equations x^{2} − dy^{2} = ±2 is solvable in integers x and y;

c) the prime over 2 in Q(\sqrt{d}) is principal. Characterizing d such that x^{2} − dy^{2} = −1 has a solution is a notorious open question,

which suggests that there may be no simple solution to the current problem.

Walsh’s argument, as presented by Wolfskill, runs as follows. Let K = Q(\sqrt{ϵ}), let α in K be such that α^{2} = ϵ. Note that the norm of ϵ is 1, whence K/Q is Galois and non-cyclic. Since α is in K we have α = r + s\sqrt{d} + t\sqrt{d′} + u\sqrt{dd′} for some rational r, s, t and u and some d′ with \sqrt{d′} in K. Let σ be the element of the Galois group of K/Q fixing \sqrt{d} but not fixing \sqrt{d′}. Then (σ(α))^{2} = σ(α^{2}) = σ(ϵ) = ϵ = α^{2}, so σ(α) = α or σ(α) = −α. If σ(α) = α then α is in Q(\sqrt{d}) but then α^{2} = ϵ contradicts the hypothesis that ϵ is a fundamental unit in Q(\sqrt{d}), so σ(α) = −α, so α = t\sqrt{d′} + u\sqrt{dd′}.

Now assume \sqrt{2} is in K, so α = t\sqrt{2} + u\sqrt{2d}, t and u rational. From α^{2} = ϵ we get that 2(t^{2} + du^{2}) = a and 4tu = b are both integers, from which it is easy to deduce that 2t = x (say) and 2u = y (say) are integers. Then (x^{2} − dy^{2})^{2} = 4(a^{2} − db^{2}) = 4, so x^{2} − dy^{2} = ±2.

Conversely, suppose x and y are positive integers such that x^{2} − dy^{2} = ±2. Note that x and y are odd. Let a = (x^{2} + dy^{2})/2, b = xy. Then a^{2} − db^{2} = 1, so a + b\sqrt{d} is a unit in Q(\sqrt{d}). Also, (\frac{x}{2} \sqrt{2} + \frac{y}{2} \sqrt{2d})^{2} = a + b\sqrt{d}, so a + b\sqrt{d} must be an odd power of the fundamental unit in Q(\sqrt{d})—otherwise, \frac{x}{2} \sqrt{2} + \frac{y}{2} \sqrt{2d} would be in Q(\sqrt{d}). So, \sqrt{2} is in Q(\sqrt{ϵ}).

99:02 (Greg Martin) Consider the following “proof” that 4680 is perfect: 4680 = 2^{3} · 3^{2} · (−5)·(−13), so σ(4680) = (1+2+2^{2}+2^{3})(1+3+3^{2})(1+(−5))(1+(−13)) = 9360 = 2×4680. Allowing the use of σ(−p^{n}) = ∑_{j=0}^{n}(−p)^{j}, is there a “spoof perfect number” with exactly 3 distinct prime factors?

Remark: If so, it must be negative.

Solution: Dennis Eichhorn found that −84 = 2^{2}(3)(−7) is spoof-perfect, and Eichhorn and Peter Montgomery independently found that −120 = 2^{3}(3)(−5) is spoof-perfect. Montgomery also found that −672 = (−2)^{5}(3)(7) leads to

σ(−672) = (1 − 2 + 4 − 8 + 16 − 32)(1 + 3)(1 + 7) = −672.

Alf van der Poorten asked whether there are any odd spoof-perfects.

John Selfridge asked whether 4680 is the smallest positive spoof-perfect.

See also 99:08, below.

99:03 (Mike Filaseta) Find m_{0} such that if m ≥ m_{0} and m(m − 1) = 2^{a}3^{b}m′ and (m′, 6) = 1 then m′ > \sqrt{m}.

Remark: See

M. Filaseta, A generalization of an irreducibility theorem of I. Schur, Analytic number theory, Vol. 1 (Allerton Park, IL, 1995), 371–396, Progr. Math. 138, Birkhauser, Boston 1996

for a similar but ineffective result derived from work of Mahler.

99:04 (Mike Filaseta) Show that every n × n integer matrix, n ≥ 2, is a sum of 3 squares of n × n integer matrices.

Remark: What is wanted is an argument more transparent than that in

Leonid N. Vaserstein, Every integral matrix is the sum of three squares, Linear and Multilinear Algebra 20 (1986) 1–4.

99:05 (Zachary Franco) Call n equidigital if each digit occurs equally often in the repeating block in the decimal expansion of 1/n. It is easy to see that if p is prime and 10 is a primitive root (mod p) then p is equidigital. Are there any equidigital primes p for which 10 is not a primitive root?

Remarks: The answer to the corresponding question in base 2 is yes; 2 is not a primitive root (mod 17) but the binary expansion of 1/17 is .˙0000111˙1.

There are equidigital composites, e.g., n = 1349 = 19 × 71.

Mike Filaseta notes that if p ≡ 11 (mod 20) is prime and 10 is of order (p − 1)/2 (mod p) then 10^{k} runs through the quadratic residues (mod p), and since there are more quadratic residues in [1, (p − 1)/2] than in [(p + 1)/2, p − 1] for such p (p ≡ 3 (mod 4)) p can’t be equidigital. For example, 1/31 = .˙03225806451612˙9 has 9 small digits and 6 large ones. Perhaps there are similar results for 10 of order (p − 1)/k for k = 3, 4, . . ..

99:06 (Kevin O’Bryant) Write √ a_{1}, a_{2}, …] for the continued square root

\frac{1}{\sqrt{a_{1} + \frac{1}{\sqrt{a_{2}+...}}}}

where a_{1}, a_{2}, … are positive integers. Every real number r, 0 < r < 1, has such an expression, and the expression is unique in the same sense as for simple continued fractions. Does 3/4 have a finite continued root?

Remark: 2/3 = √ 2, 16], 22/47 = √ 3, 1098, 2892, 410, 256].

99:07 (Bart Goddard) Let f : (0, ∞) → (0, ∞) be strictly decreasing and onto with f(1) = 1. Let g be the functional inverse f^{−1} of f. For α_{0} real and positive, define integers a_{0}, a_{1}, … and reals α_{1}, α_{2}, … by a_{j} = [α_{j}], α_{j} = g(α_{j−1} −a_{j−1}). Write (α_{0})_{f} for the sequence a_{0}, a_{1}, . . .. Let c_{0} = a_{0}, c_{1} = a_{0} + f(a_{1}), c_{2} = a_{0} + f(a_{1} + f(a_{2})), etc. Note that f(x) = 1/x gives the usual continued fraction expansion of α_{0}, and f(x) = 1/\sqrt{x} gives the expansion of 99:06.

Some interesting examples are

f(x) = x^{−5}, (\sqrt[5]{7})_{f} = (1, 1, 1, …)

f(x) = 1/Ω(ex), where Ω is the Lambert Ω-function,

(π)_{f} = (3, 3033, 23766810023426903113005, 2279, 2, 864, …)

1. Given f, which numbers have finite expansions? periodic expansions? Is it true that if f(x) = x^{−2/3} then (\sqrt[3]{3})_{f} = (˙1, 1, 1, ˙2)?

2. Is there an f such that (α)_{f} is periodic for all algebraic α of degree 3?

3. Find f such that (π)_{f} has a recognizable pattern.

4. Find f such that (e)_{f} is periodic.

5. Find conditions on f and α for lim_{n→∞} c_{n} = α.

Solution: (to question 4) Greg Martin notes that if f(x) = x^{log(e−2)/ log(e−1)} then (e)_{f} = (2, 1, 1, 1, …).

Remark: Jeff Lagarias refers to

A. Rényi, Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hungar. 8 (1957) 477–493, MR 20 #3843.

Many later papers refer to this one, as may be seen from the listing on MathSciNet.

99:08 (Greg Martin) Define a multiplicative function σ̃ (or σ^{∽} if you are left-handed) by σ̃(p^{r}) = p^{r} − p^{r−1} + p^{r−2} − ⋯ + (−1)^{r}. Note that σ̃(n) ≤ n with equality only for n = 1. Call n σ̃-perfect if 2σ̃(n) = n; examples are n = 2, 12, 40, 252, 880, 10880, and 75852. Call n σ̃-k-perfect (or, more generally, σ̃-multiply perfect) if kσ̃(n) = n for a positive integer k. Two examples of σ̃-3-perfects are n = 30240 and n = 2^{10}3^{4}5^{4}11·13^{2} ·31·61·157·521·683— there are at least 40 σ̃-3-perfects.

1. Are there any σ̃-k-perfect numbers with k ≥ 4?

2. Are there infinitely many σ̃-k-perfect numbers?

3. Are there any odd σ̃-3-perfect numbers? Any such number must be a square.

Remark: Paraphrasing email from Greg: let τ(n) = n/σ̃(n), so τ(n) = k means n is a σ̃-k-perfect number. Suppose n = p^{2k−1}m, p prime, and σ̃(p^{2k}) = q is prime, and (m, pq) = 1. Then it’s not hard to prove that τ(n) = τ(npq). In particular, if n is σ̃-k-perfect, so is npq.

Some examples of prime powers p^{2k−1} such that σ̃(p^{2k}) is prime are

2^{1}, 2^{3}, 2^{5}, 2^{9}, 3^{1}, 3^{3}, 3^{5}, 5^{3}, 7^{1}, 13^{1}.

This makes it possible to find 40 σ̃-3-perfects from the four examples 2^{3}3^{3}5^{2}7, 2^{5}3^{3}5 · 7, 2^{5}3^{5}5^{2}7^{3}13, and 2^{9}3^{3}5^{3}11 · 13 · 31.

Jeff Lagarias suggested looking at the Dirichlet series generating function for σ̃, in analogy with

∑_{n=1}^{∞} \frac{σ(n)}{n}n^{−s} = ζ(s + 1)ζ(s).

Greg finds that

∑_{n=1}^{∞} \frac{1}{τ(n)}n^{−s} = ζ(2s + 2)ζ(s)/ζ(s + 1),

but no such tidy form for ∑_{n=1}^{∞} τ(n)n^{−s}.

99:09 (Jean-Marie De Koninck) Given an integer k, k ≥ 2, not a multiple of 3, 1. prove that there is a prime whose digits sum to k,

2. prove that if k ≥ 4 then there are infinitely many primes whose digits sum to k. Remarks: Jean-Marie provided a table of values of ρ(k), the smallest prime whose

digits add up to k, for 2 ≤ k ≤ 83, k not a multiple of 3. Your editor notes that ρ(56) − ρ(55) = 2999999 − 2998999 = 1000 and asks whether there are infinitely many k with ρ(k + 1) − ρ(k) = 1000, or with ρ(k + 1) − ρ(k) = 10^{m} for some m, or whether there is an integer r with ρ(k + 1) − ρ(k) = r for infinitely many r.

Your editor further notes that ρ(34)/ρ(32) = 17989/6899 = 2.61 (to two decimals), ρ(37)/ρ(35) = 29989/8999 = 3.33, ρ(70)/ρ(68) = 189997999/59999999 = 3.17, and ρ(73)/ρ(71) = 289999999/89999999 = 3.22, and asks whether ρ(3k + 1)/ρ(3k − 1) is unbounded. Moreover, your editor also notes that ρ(34)/ρ(35) = 17989/8999 = 2.00 and ρ(70)/ρ(71) = 189997899/89999999 = 2.11 and asks whether ρ(k) > ρ(k + 1) infinitely often.

Further questions: is it true that k > 25 implies ρ(k) ≡ 9 (mod 10)? that k > 38 implies ρ(k) ≡ 99 (mod 100)? that k > 59 implies ρ(k) ≡ 999 (mod 1000)?

Jean-Marie also notes that it is trivial that ρ(k) ≥ (a + 1)10^{b} − 1, where b = [k/9] and a = k − 9b; and asks whether equality holds infinitely often. For instance, it is the case when k = 5, 7, 10, 11, 14, 16, 17, 19, 22, 23, 28, 29, 31, 35, 40.

99:10 (Jeff Lagarias) Is there a field with Galois group S_{n}, n ≥ 5, whose ring of integers has a power basis?

99:11 (Sinai Robins) Let q be real, |q| < 1. Is the function given by f(x) = ∑_{n=1}^{∞}[nx]q^{n} real analytic in x?

Remark: A starting place for the analytic properties of this and related series is

Wolfgang Schwarz, Über Potenzreihen, die irrationale Funktionen darstellen, I and II, Überblicke Mathematik, Band 6, 179–196 and 7, 7–32, MR 51 #8382-3.

See also

J. H. Loxton, A. J. van der Poorten, Arithmetic properties of certain functions in several variables. III, Bull. Austral. Math. Soc. 16 (1977) 15–47, MR 81g:10046.

99:12 (Jeff Lagarias) Given n > 3, find upper and lower bounds for the number of solutions 1 < q_{1} < ⋯ < q_{n} of the system q_{j}^{−1} ∏_{1}^{n} q_{j} ≡ 1 (mod q_{j}), j = 1, …, n.

Remark: It is known that there are only finitely many solutions for each n, in fact there is an upper bound for q_{n}, but it does not give a good estimate for the number of solutions. (2, 3, 5) is the only solution for n = 3. The problem is discussed in

Lawrence Brenton, Mi-Kyung Joo, On the system of congruences ∏_{j≠i} n_{j}≡1 (mod n_{i}), Fib. Q. 33 (1995) 258–267.

The review, MR 96k:11039, is also worth reading.