Unexpected appearance of Pythagorean triples in a homeomorphism between the 1-sphere and the extended real line

pythagorean triples I was thinking about various kinds of mappings of prime numbers and wondered in particular what prime numbers would look like when projected from the (extended) real line to the 1-sphere by a homeomorphism linking these two spaces. When I did the calculations I was amazed to find that prime numbers are mapped to a family of Pythagorean triples on the 1-sphere! This came as a complete surprise to me but I later learned that the link between stereographic projection and Pythagorean triples is already well known. Nevertheless, in this note I want to quickly record how I stumbled on this result.

onesphere Consider the three points N, Q and P in the diagram. Since they are collinear there must be a scalar t such that

P = N + t(Q - N)

Writing this equation in vector form we get

(x, 0) = (0, 1) + t\big((x_1, x_2) - (0, 1) \big)

= (x_1 t, t(x_2 - 1) + 1)

from which we deduce

x = x_1 t

\implies t = \frac{x}{x_1}

and

t(x_2 - 1) + 1 = 0

\implies t = \frac{1}{1 - x_2}

Equating these two expressions for t we get

\frac{x}{x_1} = \frac{1}{1 - x_2}

\implies x = \frac{x_1}{1 - x_2}

The function \pi(x_1, x_2) = \frac{x_1}{1 - x_2} is the homeomorphism which maps points on the 1-sphere to points on the extended real line.

I was more interested in the inverse function \pi^{-1}(x) which maps points on the extended real line to the 1-sphere. To find this, observe that

x^2 + 1 = \frac{x_1^2}{(1 - x_2)^2} + \frac{(1 - x_2)^2}{(1 - x_2)^2}

Using x_1^2 + x_2^2 = 1 we have x_1^2 = 1 - x_2^2 so the above equation can be written as

x^2 + 1 = \frac{1 - x_2^2}{(1 - x_2)^2} + \frac{(1 - 2x_2 + x_2^2)}{(1 - x_2)^2}

= \frac{2 - 2x_2}{(1 - x_2)^2} = \frac{2}{1 - x_2}

Therefore

x^2 + 1 = \frac{2}{1 - x_2}

\implies x_2 = \frac{x^2 - 1}{x^2 + 1}

and then

x = \frac{x_1}{1 - x_2}

\implies x_1 = \frac{2x}{x^2 + 1}

Therefore if x is a prime, the corresponding point on the 1-sphere is

\bigg( \frac{2x}{x^2 + 1}, \frac{x^2 - 1}{x^2 + 1} \bigg)

However, the numbers 2x, x^2 - 1 and x^2 + 1 are then Pythagorean triples, as can easily be demonstrated by showing that these terms satisfy the identity

(2x)^2 + (x^2 - 1)^2 \equiv (x^2 + 1)^2

A Euclidean-like division algorithm for converting prime reciprocals into ternary numbers

Graphic1 For the purposes of some work I was doing involving ternary numbers, I became interested in finding a quick and easily programmable method for converting prime reciprocals into ternary representation. By trial and error I found a Euclidean-like division algorithm which works well, as illustrated by the following application to the calculation of the ternary representation of the prime reciprocal \frac{1}{7}:

3 = 0 \times 7 + 3

9 = 1 \times 7 + 2

6 = 0 \times 7 + 6

18 = 2 \times 7 + 4

12 = 1 \times 7 + 5

15 = 2 \times 7 + 1

The first equation always has 3 on the left hand side and the remainder in each equation is multiplied by 3 to obtain the left-hand side of the next equation. The procedure halts when a remainder is obtained which is equal to 1. From then on, the pattern of the coefficients of the prime denominator will repeat indefinitely. In the above example a remainder of 1 is obtained at the sixth step, and the pattern will repeat from then on, so looking at the coefficients of 7 we conclude that the ternary representation of \frac{1}{7} is 0.\dot{0}1021\dot{2} where the dot notation is used to indicate that the string of digits between the dots repeats indefinitely. This is completely analogous to the fact that the decimal, i.e., base-10, representation of \frac{1}{7} has the repeating cycle structure 0.\dot{1}4285\dot{7}. Note that the cycle length is 6 in the ternary representation of \frac{1}{7} precisely because 6 is the order of 3 modulo 7. (The order of an integer modulo a prime p is the lowest power of the integer which is congruent to 1 mod p. A well known theorem of Fermat guarantees that the order of any integer modulo a prime p is at most p - 1).

A further illustration is the computation of the ternary form of \frac{1}{13}, for which the division algorithm yields

3 = 0 \times 13 + 3

9 = 0 \times 13 + 9

27 = 2 \times 13 + 1

before the remainder repeats, giving the ternary representation 0.\dot{0}0\dot{2}. The cycle length for \frac{1}{13} is 3, which is due to the fact that 3 is the order of 3 mod 13.

In general, for a prime reciprocal \frac{1}{p}, the ternary cycle length will always be the order of 3 mod p, and the cycle will repeat from the first digit after the point.

To implement the above algorithm I wrote the following Python program which reads a list of primes from a text file (in this case, the first 100 primes greater than 3), then computes the ternary representation of the corresponding prime reciprocals, depositing the output in another text file. The output for each prime reciprocal is the first cycle of ternary digits (the cycle repeats indefinitely thereafter), as well as a statement of the cycle length.

pic01

The full output from running the above program with the first hundred primes greater than 3 is shown here.

Note on a Computer Search for Primes in Arithmetic Progression by Weintraub (1977)

A paper by Weintraub, S, 1977 (Primes in arithmetic progression, BIT Numerical Mathematics, Vol 17, Issue 2, p. 239-243) implements a computer search for primes in arithmetic progression (PAPs). It refers to a number N which is set to what seems at first sight to be an arbitrary value of 16680. In this note I want to try to bring out some maths underlying this choice of N in Weintraub’s paper, and also record a brute force implementation I carried out in Microsoft Excel of an adjustment factor in an asymptotic formula by Grosswald (1982) which yields the number of PAPs less than or equal to some specified number.

The number of prime arithmetic sequences of a given length that one can hope to find is determined by the chosen values of m and N in Weintraub’s paper.

On page 241 of his paper, Weintraub says: “…it is likely that with m = 510510 [and N = 16680] there exist between 20-30 prime sequences of 16 terms…”

I was pleased to find that Weintraub’s estimate of 20-30 agrees with an asymptotic formula obtained later by Grosswald (in 1982) building on a conjecture by Hardy and Littlewood. The number of q-tuples of primes p_1, . . . , p_q in arithmetic progression, all of whose terms are less than or equal to some number x, was conjectured by Grosswald to be asymptotically equal to

\frac{D_q x^2}{2(q-1)(\log x)^q}

where the factor D_q is

\prod_{p > q} \big[\big( \frac{p}{p-1}\big)^{q-1} \cdot \frac{p - (q-1)}{p} \big] \times \prod_{p \leq q} \frac{1}{p}\big(\frac{p}{p-1}\big)^{q-1}

(see Theorem 1 in Grosswald, E, 1982, Arithmetic progressions that consist only of primes, J. Number Theory 14, p. 9-31).

When q = 16 as in Weintraub’s paper, we get D_{16} = 55651.46255350 (see below).

Using m = 510510 and N = 16680, Weintraub said on page 241 that one gets an upper prime limit of around 8 \times 10^9 (Weintraub actually said: “approximately 7.7 \times 10^9“).

Plugging in the numbers q = 16, D_{16} = 55651.46255350 and x = 8 \times 10^9 in the first formula above, we get the answer 22, i.e., there are 22 prime sequences of 16 terms, in line with Weintraub’s estimate of 20-30 on page 241 of his paper.

Weintraub was clearly aware that N = 16680 (in conjunction with m = 510510) would make approximately 20-30 prime sequences of 16 terms available to his search.

The adjustment factor of D_{16} = 55651.46255350 above can be obtained to a high degree of accuracy using a series approximation involving the zeta function (see, e.g., Caldwell, 2000, preprint, p. 11). However, I wanted to see how accurately one could calculate it by using the first one hundred thousand primes directly in Grosswald’s formula for D_q above. I did this in a Microsoft Excel sheet and got the answer D_{16} = 55651.76179. Directly using Grosswald’s formula for D_q, it was not possible to get an estimate of D_{16} accurate to the first decimal place even with one hundred thousand primes.

A note on finding more base-3 palindromic primes of the form 1 + 3^k + (3^k)^2

I stumbled across base-3 palindromes of the form 1 + 3^k + (3^k)^2 for k \in \mathbb{N} and became especially interested in them when I realised the reciprocal of any such number must belong to the middle-third Cantor set. In particular, primes of this form will be Cantor primes which I have explored before. The only examples of primes of this form I am aware of are 13 (corresponding to k = 1) and 757 (corresponding to k = 3).

I am very interested in finding more primes of this base-3 palindromic form, if there are any, or if not, I would like to see a mathematical argument which shows there cannot be any more. (Since the question of whether or not there are infinitely many palindromic primes in general is a major open problem, it would be a major breakthrough to prove there are infinitely many primes of this particular palindromic form). At the very least, it would be nice to establish some conditions on k which would eliminate a lot of cases in which 1 + 3^k + (3^k)^2 cannot be prime.

I have noticed the following four properties about them, which I will document here:

Result 1. All base-3 palindromes of the form 1 + 3^k + (3^k)^2 for k \in \mathbb{N} are such that their reciprocal belongs to the middle-third Cantor set. Therefore, in particular, all primes of this form are Cantor primes.

Proof: We have

1 + 3^k + (3^k)^2 = \frac{3^{3k} - 1}{3^k - 1}

Therefore writing p = 1 + 3^k + (3^k)^2 we have

\frac{1}{p} = \frac{3^k - 1}{3^{3k} - 1}

Using the facts that

\frac{3^k - 1}{2} = 1 + 3 + 3^2 + \cdots + 3^{k-1}

and

\frac{1}{3^{3k} - 1} = \frac{1}{3^{3k}} + \frac{1}{(3^{3k})^2} + \cdots

we can write

\frac{1}{p} = 2(1 + 3 + 3^2 + \cdots + 3^{k-1}) \{\frac{1}{3^{3k}} + \frac{1}{(3^{3k})^2} + \cdots\}

This is an expression for 1/p which corresponds to a base-3 representation involving only the digits 0 and 2, and therefore 1/p must belong to the middle-third Cantor set. QED

Result 2. The base-3 palindrome 1 + 3^k + (3^k)^2 will be divisible by 1 + 3 + 3^2 = 13 if and only if gcd(k, 3) = 1. Therefore the base-3 palindrome 1 + 3^k + (3^k)^2 cannot be a Cantor prime if k is not a multiple of 3.

Proof: Begin by considering the cyclotomic polynomial

\Phi_3(x) = 1 + x + x^2

This has as its roots the two primitive cube roots of unity

w = exp(i2\pi/3) = (-1 + \sqrt{3}i)/2

and

w^2 = exp(i4\pi/3) = (-1 - \sqrt{3}i)/2

If w is a root of 1 + x^k + (x^k)^2 then so is w^2 (since roots always occur in conjugate pairs), and in this case it must be that 1 + x + x^2 is a factor of 1 + x^k + (x^k)^2. Now there are three possibilities for k:

I. k = 3s for some s \in \{0, 1, 2, \ldots \}. In this case the polynomial 1 + x^k + (x^k)^2 becomes

1 + x^{3s} + x^{6s}

Setting x = w we get

1 + w^{3s} + w^{6s} = 1 + 1 + 1 = 3

so w is not a root of 1 + x^k + (x^k)^2 here.

II. k = 3s + 1. In this case the polynomial

1 + x^k + (x^k)^2

becomes

1 + x^{3s+1} + x^{6s+2}

Setting x = w we get

1 + w + w^2 = 0

so w is a root of 1 + x^k + (x^k)^2 here.

III. k = 3s + 2. In this case the polynomial

1 + x^k + (x^k)^2

becomes

1 + x^{3s+2} + x^{6s+4}

Setting x = w we get

1 + w^2 + w^4 = 1 + w^2 + w = 0

so w is a root of 1 + x^k + (x^k)^2 here.

There are no other possibilities, so if we set x = 3 in the polynomials 1 + x + x^2 and 1 + x^k + (x^k)^2 the result is proved. QED

Result 3. The base-3 palindrome 1 + 3^k + (3^k)^2 will be divisible by some number of the form 1 + 3^{3^r} + (3^{3^r})^2 where r \in \{0, 1, 2, \ldots\} if k is not a power of 3. Therefore the base-3 palindrome 1 + 3^k + (3^k)^2 cannot be a Cantor prime if k is not a power of 3.

Proof: Consider the polynomial  1 + x^k + (x^k)^2 and suppose that k is not a power of 3. Then we can write k = 3^r \cdot s for some integer s > 1 such that gcd(s, 3) = 1. Then

1 + x^k + (x^k)^2 = 1 + y^s + (y^s)^2

where y = x^{3^r} and the result now follows immediately from Result 2 and by setting x = 3. QED

Result 4. Any base-3 palindromic prime of the form 1 + 3^k + (3^k)^2 will be of the type 4q + 1 for q \in \mathbb{N}, and can therefore be expressed as a sum of two perfect squares m^2 + n^2 where m, n \in \mathbb{N}.

Proof: If 1 + 3^k + (3^k)^2 is prime then k must be a power of 3 and hence odd. Odd powers of 3 are always of the form 4q + 3 and even powers of 3 are always of the form 4q + 1. Therefore 1 + 3^k + (3^k)^2 will be a sum of each of these two forms, plus the number 1, and this must always give a number of the form 4q + 1. It is a well known theorem of Fermat that all primes of the form 4q + 1 can be expressed as a sum of two perfect squares. QED