Avoiding 3-Term Geometric Progressions in Hurwitz Quaternions

Megumi Asada Graduate School of Education

Rutgers University New Brunswick, NJ 08901

USA

megumi.asada@rutgers.edu

Eva Fourakis Department of Mathematics

and Statistics Williams College

Williamstown, MA 01267

USA

erf1@williams.edu

Nathan McNew Department of Mathematics

Towson University Towson, MD 21252

USA

nmcnew@towson.edu

Gwyneth Moreland

Department of Mathematics, Statistics,

and Computer Science University of Illinois, Chicago

Chicago, IL 60607

USA

gwynm@uic.edu

Bruce Fang Department of Mathematics and Statistics Williams College Williamstown, MA 01267 USA

                                         bf8@williams.edu

Sarah Manski Center for Statistical Training and Consulting Michigan State University East Lansing, MI 48824 USA

                                         manskisa@msu.edu

Steven J. Miller Department of Mathematics and Statistics Williams College Williamstown, MA 01267 USA

                                         sjm1@williams.edu
                                 Steven.Miller.MC.96@aya.yale.edu

Ajmain Yamin Department of Mathematics CUNY Graduate Center New York, NY 10016 USA

                                    ayamin@gradcenter.cuny.edu

Sindy Xin Zhang Department of Mathematics Tufts University Medford, MA 02155 USA

         sindy xin.zhang@tufts.edu

Abstract

Several recent papers have considered the problem of how large a subset of integers can be without containing any 3-term geometric progressions. This problem has also recently been generalized to rings of integers in quadratic number fields and polynomial rings over finite fields. We study the analogous problem in the Hurwitz quaternion order to see how non-commutativity affects the problem. We compute an exact formula for the density of a 3-term geometric-progression-free set of Hurwitz quaternions arising from a greedy algorithm and derive upper and lower bounds for the supremum of upper densities of 3-term geometric-progression-free sets of Hurwitz quaternions.

1 Introduction

In 1961, Rankin [9] introduced the problem of finding large sets of positive integers which avoid 3-term geometric progressions. An obvious example of such a set is the set of squarefree positive integers which has asymptotic density 6/π^{2} ≈ 0.607927. Rankin constructed a higher density geometric-progression-free set, which we denote as G_{3}^{∗}(ℕ_{+}), and obtained an exact closed-form expression for its density in terms of the Riemann ζ-function

d(G_{3}^{∗}(ℕ_{+})) = \frac{1}{ζ(2)} ∏_{n=1}^{∞} \frac{ζ(3^{n})}{ζ(2 · 3^{n})} ≈ 0.719745.

It was shown by Brown and Gordon [4] that G_{3}^{∗}(ℕ_{+}) is actually generated by a greedy algorithm; it is formed from the singleton {1} by greedily adjoining to it integers of increasing magnitude so long as the enlarged set still avoids 3-term geometric progressions. As such, we refer to G_{3}^{∗}(ℕ_{+}) as Rankin’s greedy set. Listing the elements of G_{3}^{∗}(ℕ_{+}) in increasing order yields the sequence (1, 2, 3, 5, 6, 7, …), which is OEIS \underline{A000452}.

By modifying Rankin’s greedy set, McNew [6] constructed a set of positive integers avoiding 3-term geometric progressions with asymptotic density greater than d(G_{3}^{∗}(ℕ_{+})). It remains an open problem to determine the supremum of asymptotic densities of such sets.

Variants of this problem have been studied by many authors including Riddell [10], Brown and Gordon [4], Beiglböck, Bergelson, Hindman, and Strauss [2], Nathanson and O’Bryant [7], and McNew [6]. More recently, Best, Huan, McNew, Miller, Powell, Tor, and Weinstein [3] studied analogous problems in rings of integers of quadratic number fields, while Asada, Fourakis, Manski, McNew, Miller, and Moreland [1] tackled the problems in polynomial rings over finite fields.

The purpose of this paper is to investigate this problem in a non-commutative setting, namely the Hurwitz quaternion order Q_{Hur} (see Section 2). We take a 3-term geometric progression of Hurwitz quaternions to mean a triple (a, ar, ar^{2}), where a, r ∈ Q_{Hur} \ {0} and r a non-unit. A set A ⊂ Q_{Hur} avoids 3-term geometric progressions if A^{3} does not contain any such triples. We are interested in how large such a 3-term geometric-progression-free set can be.

Throughout the paper, when A ⊂ ℕ_{+} is any set of positive integers, we denote by S(A) = {q ∈ Q_{Hur} | Nm(q) ∈ A} the set of Hurwitz quaternions whose norm is contained in the set A. We also abuse this notation slightly, writing S(N) for an integer N to mean S(N) = S([1, N]), the set of all non-zero Hurwitz quaternions whose norm is at most N.

It is easy to see that if G is any set of positive integers which avoid 3-term geometric progressions, then the set S(G) of Hurwitz quaternions is also 3-term geometric-progression-free, in the sense above. Our first result is an exact formula for the density (see Section 3) of S(G) in Q_{Hur} when G is Rankin’s greedy set G_{3}^{∗}(ℕ_{+}).

Theorem 7. The density of the set S(G_{3}^{∗}(ℕ_{+})) of Hurwitz quaternions with norm in Rankin’s greedy set G_{3}^{∗}(ℕ_{+}) is

d(S(G_{3}^{∗}(ℕ_{+}))) = \frac{f(2^{2})}{ζ(2)} ∏_{\begin{matrix}p>2 \\ prime \end{matrix}} (f(p) − \frac{f(p^{2})}{p}) ≈ 0.782643,

where

f(x) = ∏_{i=0}^{∞} (1 + \frac{1}{x^{3^{i}}} ) .

This is somewhat higher than the density of Rankin’s greedy set G_{3}^{∗}(ℕ_{+}) in ℕ_{+}, which is ≈ 0.719745.

Our second result provides upper and lower bounds on the supremum of upper densities (see Section 4) of sets of Hurwitz quaternions free of 3-term geometric progressions.

Theorem 14. The supremum \overline{m}_{Hur} of upper densities of sets of Hurwitz quaternions that avoid 3-term geometric progressions satisfies the following bounds:

0.946589 ≈ \frac{17665627}{18662400} ≤ \overline{m}_{Hur} ≤ \frac{20}{21} ≈ 0.952381.

In Section 2, we establish some asymptotic formulas for certain counts of Hurwitz quaternions which are useful for computing densities. In Section 3, we prove Theorem 7. The approach is to first prove Theorem 5, which is a general Euler product formula for densities of certain sets of the form S(G), and then apply it to the special case when G is Rankin’s greedy set G_{3}^{∗}(ℕ_{+}). In Section 4, we prove Theorem 14. The approach is to adapt and modify the arguments of McNew [6], which are used to produce the best bounds on upper densities of geometric-progression-free sets of integers, to work in the quaternionic setting. The remainder of the paper is dedicated to the quaternion greedy set G_{3}^{∗}(Q_{Hur} \ {0}). A major difference between the rational integer setting and the Hurwitz quaternion setting is the fact that the natural analogue of Rankin’s greedy set for Q_{Hur} is much more difficult to analyze. This is due to the non-commutativity of the quaternions. In Section 5 we explicate these difficulties and in Section 6 we list open questions and ways to generalize this work.

2 Combinatorics of Hurwitz quaternions

The Hamilton quaternions ℍ := {a + bi + cj + dk | a, b, c, d ∈ ℝ} constitute the noncommutative algebra over the reals generated by units i, j, and k satisfying

i^{2} = j^{2} = k^{2} = ijk = −1,
ij = −ji = k, jk = −kj = i, ki = −ik = j.

The norm of a quaternion Q = a + bi + cj + dk is Nm(Q) := a^{2} + b^{2} + c^{2} + d^{2}. A quaternion a + bi + cj + dk belongs to the Hurwitz order Q_{Hur}, or is a Hurwitz quaternion, if a, b, c, d are all in ℤ or all in ℤ + \frac{1}{2}. The norm of a Hurwitz quaternion is always a nonnegative integer.

In this section, we compute asymptotic formulas for the number of Hurwitz quaternions up to a certain norm excluding 0, and the subset of those whose norm is coprime to a given number. These formulas are used in the proofs of our main results Theorem 7 and Theorem 14. For a more in-depth discussion of the Hurwitz quaternion order, see Conway and Smith [5, Ch. 5] or Voight [12, Ch. 11].

We begin with a classical result that follows from Jacobi’s four-square theorem.

Lemma 1. The number of Hurwitz quaternions of norm N is 24 · σ_{odd}(N), where σ_{odd} is the sum-of-odd-divisors function

σ_{odd}(N) := ∑_{2∤d|N} d.

For a complete proof of this fact see, for example, the master’s thesis of Negrini [8]. The sequence of numbers (24 · σ_{odd}(N))_{N>0} = (24, 24, 96, 24, 144, …) is OEIS \underline{A004011}.

Using this lemma, we prove the following asymptotic result.

Lemma 2.

(a) The number of Hurwitz quaternions with norm less than or equal to N is

∑_{n≤N} 24 · σ_{odd}(n) = π^{2}N^{2} + O(N log N).

(b) For a fixed integer M, the number of Hurwitz quaternions with norm at most N and with norm coprime to M is

∑_{\begin{matrix}n≤N \\ gcd(n,M)=1 \end{matrix}} 24 · σ_{odd}(n) = π^{2}N^{2} · \frac{φ(2M)}{M} ∏_{p|M}(1 − p^{−2}) + O(N log N).

Proof of (a). Making use of the fact that the sum of the first k odd numbers is k^{2}, we compute

∑_{n≤N} σ_{odd}(n) = ∑_{m≤N} ∑_{\begin{matrix}d|m \\ 2∤d \end{matrix}} d = ∑_{e≤N} ∑_{\begin{matrix}d≤⌊\frac{N}{e}⌋ \\ 2∤d \end{matrix}} d = ∑_{e≤N} ⌈\frac{⌊\frac{N}{e} ⌋}{2}⌉^{2}  (write m = de)

= \frac{1}{4} ∑_{e≤N} ((\frac{N}{e} )^{2} + O (\frac{N}{e} )) = \frac{1}{4}N^{2} ∑_{e≤N} \frac{1}{e^{2}} + O (N log N)

= \frac{1}{4}N^{2} (\frac{π^{2}}{6} ) + O (N log N + N^{2} ∑_{e>N} \frac{1}{e^{2}} ) (first series converges to \frac{π^{2}}{6} )

= \frac{π^{2}}{24}N^{2} + O (N log N) .

Proof of (b). We compute

∑_{\begin{matrix}n≤N \\ gcd(n,M)=1 \end{matrix}} σ_{odd}(n) = ∑_{\begin{matrix}n≤N \\ gcd(n,M)=1 \end{matrix}} ∑_{2∤d|n} d = ∑_{\begin{matrix}e≤N \\ gcd(e,M)=1 \end{matrix}} ∑_{\begin{matrix}d≤⌊\frac{N}{e} ⌋ \\ gcd(d,2M)=1 \end{matrix}} d

= ∑_{\begin{matrix}e≤N \\ gcd(e,M)=1 \end{matrix}} ∑_{\begin{matrix}r≤2M \\ gcd(r,2M)=1 \end{matrix}} ∑_{\begin{matrix}d≤⌊\frac{N}{e} ⌋ \\ d≡r (mod 2M) \end{matrix}} d.

Since

∑_{\begin{matrix}e≤N \\ gcd(e,M)=1 \end{matrix}} ∑_{\begin{matrix}r≤2M \\ gcd(r,2M)=1 \end{matrix}} ( ∑_{\begin{matrix}d≤⌊\frac{N}{e} ⌋ \\ d≡r (mod 2M) \end{matrix}} d − ∑_{\begin{matrix}m≤⌊\frac{N}{e} ⌋ \\ 2M|m \end{matrix}} m) = O(N log N),

we see

∑_{\begin{matrix}n≤N \\ gcd(n,M)=1 \end{matrix}} σ_{odd}(n) = ∑_{\begin{matrix}e≤N \\ gcd(e,M)=1 \end{matrix}} ∑_{\begin{matrix}r≤2M \\ gcd(r,2M)=1 \end{matrix}} ∑_{\begin{matrix}m≤⌊\frac{N}{e} ⌋ \\ 2M|m \end{matrix}} m + O(N log N)

= φ(2M) ∑_{\begin{matrix}e≤N \\ gcd(e,M)=1 \end{matrix}} ∑ ; n≤⌊\frac{⌊\frac{N}{e} ⌋}{2M}⌋ 2M · n + O(N log N)

= Mφ(2M) ∑_{\begin{matrix}e≤N \\ gcd(e,M)=1 \end{matrix}} ⌊\frac{⌊\frac{N}{e} ⌋}{2M}⌋ (⌊\frac{⌊\frac{N}{e} ⌋}{2M}⌋ + 1) + O(N log N)

= N^{2} · \frac{φ(2M)}{4M} ∑_{\begin{matrix}1≤e≤∞ \\ gcd(e,M)=1 \end{matrix}} \frac{1}{e^{2}} + O(N log N).

By the inclusion-exclusion principle, expressed with the Möbius μ function, we have

∑_{\begin{matrix}1≤e≤∞ \\ gcd(e,M)=1 \end{matrix}} \frac{1}{e^{2}} = ∑_{d|M} (μ(d) · ∑_{n=1}^{∞} \frac{1}{(dn)^{2}} ) = ζ(2) ∑_{d|M} \frac{μ(d)}{d^{2}} = \frac{π^{2}}{6} ∏_{p|M}(1 − p^{−2}).

Thus,

∑_{\begin{matrix}n≤N \\ gcd(n,M)=1 \end{matrix}} σ_{odd}(n) = N^{2} · \frac{π^{2}}{24} \frac{φ(2M)}{M} ∏_{p|M}(1 − p^{−2}) + O(N log N).

3 Exact densities of sets of Hurwitz quaternions

Definition 3. Let A ⊂ Q_{Hur}. The density of A in Q_{Hur}, denoted d(A), is defined to be

d(A) := lim_{N→∞} \frac{|A ∩ S(N)|}{|S(N)|},

provided the limit exists. Here, as before, S(N) is the set of non-zero Hurwitz quaternions of norm at most N.

Example 4. If A denotes the set of Hurwitz quaternions with norm coprime to M, then by Lemma 2, we see that the density of A in Q_{Hur} is

d(A) = \frac{φ(2M)}{M} ∏_{p|M}(1 − p^{−2}).

The purpose of this section is to compute an exact formula for the density of S(G_{3}^{∗}(ℕ_{+})) in Q_{Hur}. Recall that S(G_{3}^{∗}(ℕ_{+})) is the set of Hurwitz quaternions with norm in Rankin’s greedy set G_{3}^{∗}(ℕ_{+}). The set G_{3}^{∗}(ℕ_{+}) is formed by starting with the singleton {1} and greedily adjoining to it larger positive integers which do not form 3-term geometric progressions with the previously included elements. Listing the elements of G_{3}^{∗}(ℕ_{+}) in increasing order yields the sequence (1, 2, 3, 5, 6, 7, 8, 10, 11, …), which is OEIS \underline{A000452}. Note that

G_{3}^{∗}(ℕ_{+}) = {n ∈ ℕ_{+} | ν_{p}(n) ∈ A_{3}^{∗}(ℕ_{+}) for all primes p},

where ν_{p} denotes the p-adic valuation and A_{3}^{∗}(ℕ_{+}) is the set formed by greedily including non-negative integers that do not form a 3-term arithmetic progression with the previously included elements. Brown and Gordon [4] showed that A_{3}^{∗}(ℕ_{+}) is also the set of non-negative integers whose ternary expansion does not contain the digit 2. Listing the elements of A_{3}^{∗}(ℕ_{+}) in increasing order yields the sequence (0, 1, 3, 4, 9, 10, 12, 13, …), which is OEIS \underline{A005836}.

We compute the density of S(G_{3}^{∗}(ℕ_{+})) in Q_{Hur} using the following theorem, which provides an Euler product for densities of certain kinds of sets in Q_{Hur}. We would like to thank Emma Dinowitz for helpful discussions regarding the proof of the following theorem.

Theorem 5. Let A ⊂ ℕ and let G := {n ∈ ℕ_{+} | ν_{p}(n) ∈ A for all primes p}. Then

d(S(G)) = \frac{1}{ζ(2)} (∑_{k∈A} \frac{1}{2^{2k}} ) ∏_{\begin{matrix}p>2 \\ prime \end{matrix}} (∑_{k∈A} \frac{1}{p^{k}} − \frac{1}{p} ∑_{k∈A} \frac{1}{p^{2k}} ) .

Proof. For each prime p and each positive integer N, we define

G_{p} := \{n ∈ ℕ_{+} | ν_{p}(n) ∈ A\} and G_{N} := ⋂_{\begin{matrix}p|N \\ p prime \end{matrix}} G_{p}.

For each positive integer r, write N_{r} to denote the r^{th} primorial N_{r} := p_{1}p_{2} ⋯ p_{r}. For convenience, write Σ(N) to denote Σ(N) := ∑_{n≤N} σ_{odd}(n). We compute

d(S(G)) = lim_{N→∞} \frac{1}{∑_{n≤N} σ_{odd}(n)} ∑_{n≤N} σ_{odd}(n) · 1_{G}(n)

= lim_{r→∞} lim_{N→∞} \frac{1}{Σ(N)} ∑_{n≤N} σ_{odd}(n) · 1_{G_{Nr}} (n)

= lim_{r→∞} lim_{N→∞} \frac{1}{Σ(N)} ∑_{(a_{j})_{j=1}^{r}∈ℕ^{r}} ∑_{\begin{matrix}n≤N \\ ∀j≤r, \\ ν_{p_{j}} (n)=a_{j} \end{matrix}} σ_{odd}(n) · 1_{G_{Nr}} (p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}}).

Since σ_{odd} is multiplicative, we see

d(S(G)) = lim_{r→∞} lim_{N→∞} \frac{1}{Σ(N)} ∑_{(a_{j})_{j=1}^{r}∈ℕ^{r}} ∑_{\begin{matrix}n≤N \\ ∀j≤r, \\ ν_{p_{j}} (n)=a_{j} \end{matrix}} σ_{odd} (\frac{n}{p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}}} )

· σ_{odd}(p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}})1_{G_{Nr}} (p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}})

= lim_{r→∞} ∑_{(a_{j})_{j=1}^{r}∈ℕ^{r}} lim_{N→∞} \frac{1}{Σ(N)} ∑_{\begin{matrix}m≤N/p_{1}^{a_{1}}···p_{r}^{ar} \\ gcd(m,N_{r})=1 \end{matrix}} σ_{odd}(m)

· σ_{odd}(p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}})1_{G_{Nr}} (p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}}).

By Lemma 2,

d(S(G)) = lim_{r→∞} ∑_{(a_{j})_{j=1}^{r}∈ℕ^{r}} ( lim_{N→∞} \frac{(\frac{N}{p_{1}^{a_{1}}···p_{r}^{ar}} )^{2} · \frac{π^{2}}{24} \frac{φ(2N_{r})}{N_{r}} ∏_{j≤r}(1 − p_{j}^{−2}) + O(N log N)}{N^{2} · \frac{π^{2}}{24} + O(N log N)})

· σ_{odd}(p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}})1_{G_{Nr}} (p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}}).

We see

d(S(G)) = lim_{r→∞} ∑_{(a_{j})_{j=1}^{r}∈ℕ^{r}} (\frac{φ(2N_{r})}{N_{r}} ∏_{j≤r} \frac{1}{p^{2a_{j}}} (1 − p_{j}^{−2})) · σ_{odd}(p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}})1_{G_{Nr}} (p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}})

= \frac{1}{ζ(2)} lim_{r→∞} \frac{φ(2N_{r})}{N_{r}} ∑_{(a_{j})_{j=1}^{r}∈ℕ^{r}} \frac{σ_{odd}(p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}}) · 1_{G_{Nr}} (p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}})}{p_{1}^{2a_{1}} ⋯ p_{r}^{2a_{r}}}

= \frac{1}{ζ(2)} lim_{r→∞} \frac{φ(2N_{r})}{N_{r}} ∏_{j≤r} ∑_{k=0}^{∞} \frac{σ_{odd}(p_{j}^{k}) · 1_{G_{p_{j}}} (p_{j}^{k})}{p_{j}^{2k}}

= \frac{2}{ζ(2)} ∏_{p prime} (1 − \frac{1}{p}) ∑_{k=0}^{∞} \frac{σ_{odd}(p^{k}) · 1_{G}(p^{k})}{p^{2k}} = \frac{2}{ζ(2)} ∏_{p prime} (1 − \frac{1}{p}) ∑_{k∈A} \frac{σ_{odd}(p^{k})}{p^{2k}}.

Using the fact σ_{odd}(2^{k}) = 1 and σ_{odd}(p^{k}) = \frac{p^{k+1}−1}{p−1} for primes p > 2, we get

d(S(G)) = \frac{1}{ζ(2)} (∑_{k∈A} \frac{1}{2^{2k}} ) ∏_{\begin{matrix}p>2 \\ prime \end{matrix}} (∑_{k∈A} \frac{1}{p^{k}} − \frac{1}{p} ∑_{k∈A} \frac{1}{p^{2k}} ) .

Example 6. If A denotes the set of all Hurwitz quaternions with squarefree norm, then by Theorem 5 and the fact that n is squarefree if and only if ν_{p}(n) ∈ {0, 1} for all primes p, we see

d(A) = \frac{1}{ζ(2)} (1 + \frac{1}{2^{2}} ) ∏_{\begin{matrix}p>2 \\ prime \end{matrix}} (1 + \frac{1}{p} − \frac{1}{p} − \frac{1}{p^{3}} )

= \frac{1}{ζ(2)ζ(3)} \frac{1 + 1/2^{2}}{1 − 1/2^{3}} = \frac{60}{7π^{2}ζ(3)} ≈ 0.722484.

Now, we use Theorem 5 to compute the density of S(G_{3}^{∗}(ℕ_{+})).

Theorem 7. The density of the set S(G_{3}^{∗}(ℕ_{+})) of Hurwitz quaternions with norm in Rankin’s greedy set G_{3}^{∗}(ℕ_{+}) is

d(S(G_{3}^{∗}(ℕ_{+}))) = \frac{f(2^{2})}{ζ(2)} ∏_{\begin{matrix}p>2 \\ prime \end{matrix}} (f(p) − \frac{f(p^{2})}{p}) ≈ 0.782643,

where

f(x) = ∏_{i=0}^{∞} (1 + \frac{1}{x^{3^{i}}} ) .

Proof. By Theorem 5 we see

d(S(G_{3}^{∗}(ℕ_{+}))) = \frac{1}{ζ(2)} ( ∑_{k∈A_{3}^{∗}(ℕ_{+})} \frac{1}{2^{2k}} ) · ∏_{\begin{matrix}p>2 \\ prime \end{matrix}} ( ∑_{k∈A_{3}^{∗}(ℕ_{+})} \frac{1}{p^{k}} − \frac{1}{p} ∑_{k∈A_{3}^{∗}(ℕ_{+})} \frac{1}{p^{2k}} )

= \frac{1}{ζ(2)} ∏_{j=0}^{∞} (1 + \frac{1}{2^{2·3^{j}}} ) · ∏_{\begin{matrix}p>2 \\ prime \end{matrix}} (∏_{j=0}^{∞} (1 + \frac{1}{p^{3^{j}}} ) − \frac{1}{p} ∏_{j=0}^{∞} (1 + \frac{1}{p^{2·3^{j}}} ))

= \frac{f(2^{2})}{ζ(2)} ∏_{\begin{matrix}p>2 \\ prime \end{matrix}} (f(p) − \frac{f(p^{2})}{p}) ,

where in the second line we use the fact that A_{3}^{∗}(ℕ_{+}) is the set of non-negative integers whose ternary expansion do not contain the digit 2 [4].

This product converges and is estimated to be ≈ 0.782643 through Mathematica.

4 Bounds on the supremum of upper densities

We now consider how large a set of Hurwitz quaternions can be while avoiding 3-term geometric progressions. We make this question precise, as follows.

Definition 8. Let A ⊂ Q_{Hur}. The upper and lower densities of A in Q_{Hur} are defined as

\overline{d}(A) := lim sup_{N→∞} \frac{|A ∩ S(N)|}{|S(N)|} and \underline{d}(A) := lim inf_{N→∞} \frac{|A ∩ S(N)|}{|S(N)|},

respectively. Here, S(N) is the set of non-zero Hurwitz quaternions of norm at most N.

Question 9. What is the supremum of upper densities of sets of Hurwitz quaternions that avoids 3-term geometric progressions?

We answer this question by obtaining upper and lower bounds for the supremum of upper densities of sets of Hurwitz quaternions avoiding 3-term geometric progressions.

4.1 Lower bound

For each N ∈ ℕ_{+}, let

T_{N} := ((\frac{N}{48}, \frac{N}{45}] ∪ (\frac{N}{40}, \frac{N}{36}] ∪ (\frac{N}{32}, \frac{N}{27}] ∪ (\frac{N}{24}, \frac{N}{12}] ∪ (\frac{N}{9} , \frac{N}{8} ] ∪ (\frac{N}{4} , N]) ∩ ℕ_{+}.

By Lemma 2 we have

|S(T_{N})| = |S((N/4, N])| + |S((N/9, N/8])| + |S((N/24, N/12])|
+ |S((N/32, N/27])| + |S((N/40, N/36])| + |S((N/48, N/45])|
= R_{N} + r_{N},

where

R_{N} := \frac{17665627}{18662400}π^{2}N^{2} and r_{N} := O(N log N).

Indeed,

\frac{17665627}{18662400} = (1^{2} − \frac{1}{4^{2}} ) + (\frac{1}{8^{2}} − \frac{1}{9^{2}} ) + (\frac{1}{12^{2}} − \frac{1}{24^{2}} )

+ (\frac{1}{27^{2}} − \frac{1}{32^{2}} ) + (\frac{1}{36^{2}} − \frac{1}{40^{2}} ) + (\frac{1}{45^{2}} − \frac{1}{48^{2}} ) .

Now, write S to denote

S := ⨆_{i=1}^{∞} T_{N_{i}}, where N_{i} = 48^{2^{i}} for each i ∈ ℕ.

McNew [6, proof of Thm. 3.1] showed that S is free of geometric progressions with integral ratio. Thus, S(S) is a set of Hurwitz quaternions that avoids 3-term geometric progressions. We compute the upper density of S(S) in Q_{Hur}, thereby obtaining a lower bound for the supremum of upper densities of sets of Hurwitz quaternions avoiding 3-term geometric progressions.

Lemma 10. The upper density of S(S) in Q_{Hur} is

\overline{d}(S(S)) = \frac{17665627}{18662400} ≈ 0.946589.

Proof. By the definition of upper density and by Lemma 2, we see that

\overline{d}(S(S)) = lim sup_{N→∞} \frac{|S(S) ∩ S(N)|}{|S(N)|} = lim_{k→∞} \frac{| ⨆_{i=1}^{k} S(T_{N_{i}})|}{|S(N_{k})|}

= lim_{k→∞} \frac{R_{N_{k}} + R_{N_{k−1}} + R_{N_{k−2}} + ⋯ + R_{N_{1}}}{π^{2}N_{k}^{2} + O(N_{k}logN_{k})} + lim_{k→∞} \frac{r_{N_{k}} + r_{N_{k−1}} + r_{N_{k−2}} + ⋯ + r_{N_{1}}}{π^{2}N_{k}^{2} + O(N_{k}logN_{k})} .

We first argue that the second limit term in the above expression is zero. Notice that

k · O(1) ≤ r_{N_{k}} + r_{N_{k−1}} + r_{N_{k−2}} + ⋯ + r_{N_{1}} ≤ k · O(N_{k}logN_{k}).

Since N_{k} = 48^{2^{k}}, we have

lim_{k→∞} \frac{k · O(1)}{π^{2}N_{k}^{2} + O(N_{k}logN_{k})} = 0 and lim_{k→∞} \frac{k · O(N_{k}logN_{k})}{π^{2}N_{k}^{2} + O(N_{k}logN_{k})} = 0.

Hence,

\overline{d}(S(S)) = lim_{k→∞} \frac{R_{N_{k}} + R_{N_{k−1}} + R_{N_{k−2}} + ⋯ + R_{N_{1}}}{π^{2}N_{k}^{2} + O(N_{k}logN_{k})} + 0

= lim_{k→∞} (1 + \frac{1}{(48^{2^{k−1}})^{2}} + \frac{1}{(48^{2^{k−1}+2^{k−2}})^{2}} + ⋯ + \frac{1}{(48^{2^{k−1}+2^{k−2}+···+2})^{2}} )

· lim_{k→∞} \frac{R_{N_{k}}}{π^{2}N_{k}^{2} + O(N_{k}logN_{k})}.

Notice that

0 ≤ \frac{1}{(48^{2^{k−1}})^{2}} + \frac{1}{(48^{2^{k−1}+2^{k−2}})^{2}} + ⋯ + \frac{1}{(48^{2^{k−1}+2^{k−2}+···+2})^{2}} ≤ \frac{k − 1}{(48^{2^{k−1}})^{2}} ⟶_{k→∞} 0,

so the first limit above converges to 1 and we find that

\overline{d}(S(S)) = 1 · lim_{k→∞} \frac{R_{N_{k}}}{π^{2}N_{k}^{2} + O(N_{k}logN_{k})} = \frac{17665627}{18662400}.

4.2 Upper bound

The approach we use to obtain an upper bound is similar to the approach used by McNew [6] in the classical setting. Namely, we identify a large collection of disjoint 3-term geometric progressions from which at least one term of each progression must be excluded.

Definition 11. Two 3-term geometric progressions of Hurwitz quaternions (b_{1}, b_{1}r_{1}, b_{1}r_{1}^{2}) and (b_{2}, b_{2}r_{2}, b_{2}r_{2}^{2}) are disjoint if

{b_{1}, b_{1}r_{1}, b_{1}r_{1}^{2}} ∩ {b_{2}, b_{2}r_{2}, b_{2}r_{2}^{2}} = ∅.

Fix a Hurwitz quaternion R of norm 2. For example, we can take R = 1 + i. For each n ∈ ℕ and N ∈ ℕ_{+}, write E_{n}(N) to denote

E_{n}(N) := {(bR^{3n}, bR^{3n+1}, bR^{3n+2}) | 2 ∤ Nm(b) ≤ N/2^{3n+2}}.

Note that E_{n}(N) is empty if N < 2^{3n+2}. The cardinality of E_{n}(N) is equal to the number of Hurwitz quaternions with norm less than or equal to N/2^{3n+2} and coprime to 2. By Lemma 2, for each fixed n ∈ ℕ,

|E_{n}(N)| = π^{2} (\frac{N}{2^{3n+2}} )^{2} · \frac{3}{4} + O(N log N).

Lemma 12. The union

E(N) := ⋃_{n=0}^{∞} E_{n}(N)

consists of disjoint 3-term geometric progressions contained in S(N)^{3}. Its cardinality is

|E(N)| = π^{2}N^{2} · \frac{1}{21} + O(N(log N)^{2}).

Proof. For every Hurwitz quaternion Q ∈ Q_{Hur}, there is a unique way to write Q as Q = bR^{m} for some b ∈ Q_{Hur} with 2 ∤ Nm(b) and m ∈ ℕ. This implies that E(N) consists of disjoint 3-term geometric progressions. The fact that E(N) ⊂ S(N)^{3} is obvious.

Note that E_{n}(N) ∩ E_{m}(N) = ∅ for n ≠ m ∈ ℕ. Combined with the fact that E_{n}(N) is empty for N < 2^{3n+2}, we see

E(N) = ⨆_{n=0}^{B(N)} E_{n}(N), where B(N) := ⌈\frac{1}{3}(log_{2}(N) − 2)⌉ .

where log_{2} N denotes the logarithm base 2. Thus,

|E(N)| = ∑_{n=0}^{B(N)} (π^{2} (\frac{N}{2^{3n+2}} )^{2} · \frac{3}{4} + O(N log N))

= π^{2}N^{2} · \frac{3}{4^{3}} ∑_{n=0}^{B(N)} (\frac{1}{4^{3}} )^{n} + O(N(log N)^{2}) = π^{2}N^{2} · \frac{1}{21} + O(N(log N)^{2}).

Lemma 13. Let A ⊂ Q_{Hur} be any set of Hurwitz quaternions avoiding 3-term geometric progressions. Then

\overline{d}(A) ≤ \frac{20}{21}.

Proof. Observe |A ∩ S(N)| = |S(N)| − |S(N) \ A|. Since, E(N) consists of 3-term geometric progressions in S(N), at least one term from each element of E(N) must be contained in S(N)\A. Since all of the 3-term geometric progressions in E(N) are disjoint, the cardinality of S(N) \ A is at least the cardinality of E(N). By Lemma 12,

|S(N) \ A| ≥ π^{2}N^{2} · \frac{1}{21} + O(N(log N)^{2}).

Thus,

\overline{d}(A) = lim sup_{N→∞} \frac{|A ∩ S(N)|}{|S(N)|} = lim sup_{N→∞} \frac{|S(N)| − |S(N) \ A|}{|S(N)|}

≤ 1 − lim inf_{n→∞} \frac{π^{2}N^{2} · \frac{1}{21} + O(N(log N)^{2})}{π^{2}N^{2} + O(N log N)} = \frac{20}{21}.

We have finally arrived at our answer to Question 9.

Theorem 14. The supremum \overline{m}_{Hur} of upper densities of sets of Hurwitz quaternions that avoid 3-term geometric progressions satisfies the following bounds:

0.946589 ≈ \frac{17665627}{18662400} ≤ \overline{m}_{Hur} ≤ \frac{20}{21} ≈ 0.952381.

Proof. Combine Lemma 10 and Lemma 13.

5 The quaternion greedy set

In Section 3, we computed an exact formula for the density of the set of Hurwitz quaternions S(G_{3}^{∗}(ℕ_{+})) with norm in Rankin’s greedy set G_{3}^{∗}(ℕ_{+}). It is natural to consider a different set of Hurwitz quaternions avoiding 3-term geometric progressions that is constructed by a greedy algorithm in a different way. Namely, consider the set of Hurwitz quaternions formed by including Hurwitz quaternions of increasing norms so long as they do not form a geometric progression with elements of smaller norms already included in the set. This process begins with including all the units, or Hurwitz quaternions of norm 1, and then considers progressively larger norms. The set constructed in this way is well-defined because including a particular quaternion of a given norm, n, does not create a geometric progression with any other quaternions of norm n since unit ratios are not allowed. We call this set the quaternion greedy set and denote it as G_{3}^{∗}(Q_{Hur} \ {0}). The following observation is an immediate consequence of this definition.

Proposition 15. Any Hurwitz quaternion which is not the third term of a 3-term geometric progression is contained in the quaternion greedy set G_{3}^{∗}(Q_{Hur} \ {0}).

Question 16. What is the (upper/lower) density of G_{3}^{∗}(Q_{Hur} \ {0})?

We are not able to answer Question 16 completely. However, the following proposition gives a lower bound for the density of G_{3}^{∗}(Q_{Hur} \ {0}).

Proposition 17. The quaternion greedy set G_{3}^{∗}(Q_{Hur} \ {0}) contains the set of Hurwitz quaternions whose norm is squarefree. Thus, the lower density of G_{3}^{∗}(Q_{Hur} \ {0}) in Q_{Hur} is at least

\underline{d}(G_{3}^{∗}(Q_{Hur} \ \{0\})) ≥ \frac{60}{7π^{2}ζ(3)} ≈ 0.722484.

Proof. If Q is a Hurwitz quaternion whose norm is squarefree, then Q cannot be the third term in a 3-term geometric progression, and thus by Proposition 15 must be included in the quaternion greedy set. The lower bound for the density follows from Example 6.

In the remainder of this section, we attempt to convince the reader that Question 16 is hard. One may try to tackle Question 16 via the same method used to compute the density of S(G_{3}^{∗}(ℕ_{+})). However, step zero of this method would be to realize G_{3}^{∗}(Q_{Hur} \ {0}) as the set of Hurwitz quaternions whose norm is contained in a given set G ⊂ ℕ_{+}. This is not possible, as shown by the following proposition.

Proposition 18. The quaternion greedy set is not equal to S(G) for any G ⊂ ℕ_{+}.

We postpone the proof of Proposition 18 to the end of this section.

Another approach to Question 16 is to try and relate the quaternion greedy set G_{3}^{∗}(Q_{Hur} \ {0}) to S(G_{3}^{∗}(ℕ_{+})). One might hope that G_{3}^{∗}(Q_{Hur}\{0}) would contain or be contained within S(G_{3}^{∗}(ℕ_{+})) (with possibly finitely many exceptions). If this were true, then one would be able to bound the density of G_{3}^{∗}(Q_{Hur} \ {0}) in terms of the already computed density of S(G_{3}^{∗}(ℕ_{+})). However, this is false, as shown by the following proposition.

Proposition 19. There are infinitely many Hurwitz quaternions in both complement sets G_{3}^{∗}(Q_{Hur} \ {0}) \ S(G_{3}^{∗}(ℕ_{+})) and S(G_{3}^{∗}(ℕ_{+})) \ G_{3}^{∗}(Q_{Hur} \ {0}).

We postpone the proof of Proposition 19 until the end of this section. The proof provides infinitely many such Hurwitz quaternions explicitly.

A key step in establishing both Proposition 18 and Proposition 19 is realizing that there exist Hurwitz quaternions of norm r^{2} > 0 that cannot be written as the square of a Hurwitz quaternion of norm r multiplied by a unit on the left.

Proposition 20. Suppose r ∈ ℕ_{+} is a positive integer such that either

• r cannot be represented as the sum of three integer squares, or

• r is divisible by an odd integer greater than 24.

Then there exists a Hurwitz quaternion Q of norm Nm(Q) = r^{2} such that Q cannot be written in the form Q = UR^{2} for any unit U ∈ Q_{Hur} and any R ∈ Q_{Hur} of norm Nm(R) = r. In the first case, Q = r is such a Hurwitz quaternion.

Proof when r is not a sum of 3 squares. Let r ∈ ℕ_{+} be such that r cannot be represented as the sum of three integer squares. Suppose for contradiction that r = UR^{2} for some unit U ∈ Q_{Hur} and R ∈ Q_{Hur} of Nm(R) = r. Then U^{−1}r = R^{2}. Suppose that U^{−1} = a+bi+cj+dk and R = w + xi + yj + zk. Then, solving the equation U^{−1}r = R^{2}, we find that a = \frac{w^{2}−x^{2}−y^{2}−z^{2}}{r}, b = \frac{2wx}{r}, c = \frac{2wy}{r}, d = \frac{2wz}{r}. It is a consequence of Lagrange’s three-square theorem that the set of integers that cannot be represented as a sum of three integer squares is closed under multiplication by 4. Since Nm(R) = r cannot be represented as the sum of three integer squares, we must have that w, x, y, z are all nonzero. Since w, x, y, z are nonzero, then b, c, d are nonzero; moreover, as U^{−1} = a + bi + cj + dk is a unit in Q_{Hur}, then a is also nonzero, thus a, b, c, d ∈ \{±\frac{1}{2}\}. Then, x = ±\frac{r}{4w}, y = ±\frac{r}{4w}, and z = ±\frac{r}{4w}. Substituting into \frac{w^{2}−x^{2}−y^{2}−z^{2}}{r} = ±\frac{1}{2} and solving the equation, we find that w = ±\frac{\sqrt{r}}{2} or w = ±\frac{\sqrt{3r}}{2}. We know that r cannot be represented as the sum of three integer squares; hence, r is not an integer square and w ≠ ±\frac{\sqrt{r}}{2}. We also know w = ±\frac{\sqrt{3r}}{2} ∈ ℤ or ℤ + \frac{1}{2} if and only if r = 3l^{2} for some l ∈ ℤ. However, this implies that r can be represented as the sum of three integer squares, which is a contradiction.

Proof when r has an odd divisor > 24. By Lemma 1, the number of Hurwitz quaternions Q, which can be written as Q = UR^{2} where U ∈ Q_{Hur} is a unit and R ∈ Q_{Hur} has norm Nm(R) = r is ≤ 24^{2} · σ_{odd}(r). Thus, to show there exists Hurwitz quaternions Q of norm Nm(Q) = r^{2}, which cannot be written in this form, it suffices to show 24·σ_{odd}(r) < σ_{odd}(r^{2}).

Let D be the greatest odd divisor of r. By hypothesis, D > 24. Thus, we have

24 · σ_{odd}(r) < ∑_{2∤d|r} D · d ≤ ∑_{2∤d|r^{2}} d = σ_{odd}(r^{2}),

as required.

Proposition 21. Let p be a rational prime number. Suppose Q is a Hurwitz quaternion of norm Nm(Q) = p^{2} such that Q cannot be written in the form Q = UR^{2} for any unit U ∈ Q_{Hur} and any R ∈ Q_{Hur} of norm Nm(R) = p. Then Q ∈ G_{3}^{∗}(Q_{Hur} \ {0}) \ S(G_{3}^{∗}(ℕ_{+})) and Q^{2} ∈ S(G_{3}^{∗}(ℕ_{+})) \ G_{3}^{∗}(Q_{Hur} \ {0}).

Proof. In light of Proposition 15, in order to prove that Q ∈ G_{3}^{∗}(Q_{Hur} \ {0}), it suffices to prove that Q is not the third term of any 3-term geometric progression. Suppose for contradiction that Q = br^{2} for some b, r ∈ Q_{Hur} \ {0} with r a non-unit. Then we would have p^{2} = Nm(Q) = Nm(b) · Nm(r)^{2}. Since p is prime, Nm(b), Nm(r) ∈ ℕ_{+} and Nm(r) > 1, we see Nm(r) = p and Nm(b) = 1. Thus, b is a unit, and r has norm p, contradicting the supposition that Q cannot be written in the form Q = UR^{2}. Thus, Q ∈ G_{3}^{∗}(Q_{Hur} \ {0}).

To show that Q ∈ G_{3}^{∗}(Q_{Hur} \{0})\S(G_{3}^{∗}(ℕ_{+})), it remains to prove Q ∉ S(G_{3}^{∗}(ℕ_{+})). Since Nm(Q) = p^{2}, and 2 ∉ A_{3}^{∗}(ℕ_{+}), we know Q ∉ S(G_{3}^{∗}(ℕ_{+})).

The norm of Q^{2} is Nm(Q^{2}) = p^{4} and 4 ∈ A_{3}^{∗}(ℕ_{+}), so Q^{2} ∈ S(G_{3}^{∗}(ℕ_{+})). We already know Q ∈ G_{3}^{∗}(Q_{Hur} \ {0}). Since both the first and second terms of the 3-term geometric progression (1, Q, Q^{2}) are in G_{3}^{∗}(Q_{Hur} \ {0}), we see that Q^{2} ∉ G_{3}^{∗}(Q_{Hur} \ {0}). Thus, Q^{2} ∈ S(G_{3}^{∗}(ℕ_{+})) \ G_{3}^{∗}(Q_{Hur} \ {0}).

Armed with Proposition 20 and Proposition 21, we can now prove Proposition 18 and Proposition 19.

Proof of Proposition 18. Since 7 is not a sum of three squares, we know by Proposition 20 and Proposition 21 that 7 ∈ G_{3}^{∗}(Q_{Hur} \ {0}). Note Q = 2 + i + j + k is a Hurwitz quaternion of norm 7. By Proposition 17, Q ∈ G_{3}^{∗}(Q_{Hur} \{0}). Since both 1 and Q are in G_{3}^{∗}(Q_{Hur} \{0}), the third term Q^{2} of the 3-term geometric progression (1, Q, Q^{2}) cannot be in G_{3}^{∗}(Q_{Hur} \{0}). Thus, G_{3}^{∗}(Q_{Hur} \ {0}) contains some Hurwitz quaternions of norm 7^{2}, but not all. Therefore, G_{3}^{∗}(Q_{Hur} \ {0}) cannot be S(G) for some G ⊂ ℕ_{+}.

Proof of Proposition 19. This follows from Proposition 20 and Proposition 21. Note that as p ranges over the infinitely many primes that cannot be represented as the sum of three integer squares, Proposition 20 and Proposition 21 imply that p ∈ G_{3}^{∗}(Q_{Hur} \ {0}) \ S(G_{3}^{∗}(ℕ_{+})) and p^{2} ∈ S(G_{3}^{∗}(ℕ_{+})) \ G_{3}^{∗}(Q_{Hur} \ {0}). This provides an explicit list of infinitely many examples in both complements.

In conclusion, there is no clear relationship between G_{3}^{∗}(Q_{Hur} \ {0}) and S(G_{3}^{∗}(ℕ_{+})). One may try to systematically describe the inclusions and exclusions necessary to transform S(G_{3}^{∗}(ℤ)) to G_{3}^{∗}(Q_{Hur} \ {0}), but this appears to be hard to predict or keep track of. Consequently, we do not know whether the density of G_{3}^{∗}(Q_{Hur} \{0}) in Q_{Hur} is greater than or less than the density of S(G_{3}^{∗}(ℕ_{+})) in Q_{Hur}. We also cannot make any computational estimate of the density of the quaternion greedy set as we do not even have a quick way of testing whether a given Hurwitz quaternion is included in G_{3}^{∗}(Q_{Hur} \ {0}).

6 Future work

As discussed in Section 5, the nature of the quaternion greedy set G_{3}^{∗}(Q_{Hur} \ {0}) is quite mysterious. Fundamentally, it is the non-commutativity of the Hurwitz quaternions which makes the quaternion greedy set so difficult to analyze. We record here several questions about G_{3}^{∗}(Q_{Hur} \ {0}) that remain open.

Question 22. Does G_{3}^{∗}(Q_{Hur} \ {0}) have an asymptotic density?

Question 23. Is the (lower/upper) density of G_{3}^{∗}(Q_{Hur} \ {0}) greater than d(S(G_{3}^{∗}(ℕ_{+})))?

Question 24. Is there an alternative characterization of the quaternion greedy set? Is there an efficient algorithm that tests membership in G_{3}^{∗}(Q_{Hur} \ {0})?

Next, we introduce a general framework in which questions about avoiding geometric progressions can be studied. Let B be a cancellative, normed monoid. This means B is a monoid which satisfies the cancellation property, and B comes equipped with a monoid homomorphism N : B → ℕ_{+} which we call the norm. Suppose that for each N ∈ ℕ_{+}, the set S_{B}(N) of elements in B with norm ≤ N is finite. We define the asymptotic density of a set A ⊂ B in B to be

d_{B}(A) := lim_{N→∞} \frac{|A ∩ S_{B}(N)|}{|S_{B}(N)|}

if it exists. The upper density \overline{d}_{B}(A) is defined similarly, except lim is replaced with lim sup.

Let U(B) be the universal enveloping group. This is the group with generators given by the elements of B and relations given by the full multiplication table of B. Since B is cancellative, the natural monoid homomorphism B → U(B) is injective, and we regard B as a subset of U(B) via this map. The norm N : B → ℕ_{+} naturally extends to a group homomorphism U(N) : U(B) → ℚ_{+}, which we also call the norm.

Let R ⊂ U(B) be a subset. A k-term geometric progression in B with ratio in R is a k-tuple (b_{1}, b_{2}, ⋯, b_{k}) ∈ B^{k}, where

b_{1}^{−1}b_{2} = b_{2}^{−1}b_{3} = … = b_{k−1}^{−1}b_{k} ∈ R.

A set S ⊂ B is said to avoid k-term geometric progressions with ratio in R if S^{k} does not contain any such k-tuples. Now we define the constants

m_{k}(B, R) := sup \{d_{B}(S) | \begin{matrix}S ⊂ B avoids k-term geometric progressions \\ with ratio in R, and d_{B}(S) exists \end{matrix} \} and
\overline{m}_{k}(B, R) := sup \{\overline{d}_{B}(S) | S ⊂ B avoids k-term geometric progressions with ratio in R\} .

It is clear from the definitions that m_{k}(B, R) ≤ \overline{m}_{k}(B, R). Moreover, both m_{k}(B, R) and \overline{m}_{k}(B, R) are increasing with respect to k and decreasing with respect to R.

Question 25. What is the value of m_{k}(B, R) and \overline{m}_{k}(B, R) for different choices of length k, normed monoid B and forbidden ratio set R?

In this paper, we obtained upper and lower bounds for m_{k}(B, R) and \overline{m}_{k}(B, R) when k = 3, B = Q_{Hur} \ {0} and R = Q_{Hur} \ S(1). Indeed, we have

0.782643 ≤ m_{Hur} := m_{3}(Q_{Hur} \ {0}, Q_{Hur} \ S(1)), and  (Theorem 7)
0.946589 ≤ \overline{m}_{Hur} := \overline{m}_{3}(Q_{Hur} \ \{0\}, Q_{Hur} \ S(1)) ≤ 0.952381.  (Theorem 14)

For any G ⊂ ℕ, write S_{B}(G) to denote the set of elements of B with norm in G. Since G_{k}^{∗}(ℕ_{+}) avoids k-term geometric progressions with rational ratio, we get that S_{B}(G_{k}^{∗}(ℕ_{+})) avoids k-term geometric progressions with ratio in R for any forbidden ratio set R ⊂ U(B). Thus, if d_{B}(S_{B}(G_{k}^{∗}(ℕ_{+}))) exists, it serves as a lower bound for m_{k}(B, R) for all possible forbidden ratio sets R.

Question 26. Does S_{B}(G_{k}^{∗}(ℕ_{+})) have an asymptotic density in B? If yes, compute it.

Theorem 7 answers Question 26 when k = 3 and B = Q_{Hur} \ {0}.

Now we generalize the definition of the quaternion greedy set. Suppose R is a subset of U(B) that avoids elements of norm 1. We define a greedy set of elements of B avoiding kterm geometric progressions with ratio in R as follows. Start with the set S_{B}(1) of elements of B of norm 1 and adjoin to it elements of B of increasing norm so long as the enlarged set continues to avoid k-term geometric progressions with ratio in R. This is a well-defined procedure because R does not contain any elements of norm 1. The resulting greedy set is denoted by G_{k}^{∗}(B, R). Note G_{3}^{∗}(ℕ_{+}) = G_{3}^{∗}(ℕ_{+}, ℕ_{>1}) = G_{3}^{∗}(ℕ_{+}, ℚ_{>1}), as observed by Brown and Gordon [4] and G_{3}^{∗}(Q_{Hur} \ {0}) = G_{3}^{∗}(Q_{Hur} \ {0}, Q_{Hur} \ S(1)).

Question 27. Repeat Questions 22 - 24 with G_{3}^{∗}(Q_{Hur} \ {0}) and S(G_{3}^{∗}(ℕ_{+})) replaced by G_{k}^{∗}(B, R) and S_{B}(G_{k}^{∗}(ℕ_{+})) respectively.

It would be interesting to study all the above questions when B = O \ {0} where O is a maximal order in the octonions 𝕆, as this is a non-associative setting. Even in the Hurwitz quaternion setting B = Q_{Hur} \ {0}, it would be interesting to vary the forbidden ratio set R from Q_{Hur} \ S(1) to ℕ_{>1}^{×}, ℚ_{>1}^{×} or {Q ∈ ℍ^{×} | Nm(Q) > 1}.

7 Acknowledgments

This research was conducted as part of the 2015 SMALL REU program and the 2022 Polymath Jr. program. The authors were partially supported by NSF grants DMS 1347804, DMS 1265673, DMS 1561945, DMS 2218374, and by Williams College. The authors thank Emma Dinowitz for helpful discussions regarding the proof of Theorem 5 and the suggestions of the anonymous referee which greatly improved the exposition of the paper.

References

[1] M. Asada, E. Fourakis, S. Manski, N. McNew, S. J. Miller, and G. Moreland, Subsets of 𝔽_{q}[x] free of 3-term geometric progressions, Finite Fields Appl. 44 (2017), 135–147.

[2] M. Beiglböck, V. Bergelson, N. Hindman, and D. Strauss, Multiplicative structures in additively large sets, J. Combin. Theory Ser. A 113 (2006), 1219–1242.

[3] A. Best, K. Huan, N. McNew, S. J. Miller, J. Powell, K. Tor, and M. Weinstein, Geometric-progression-free sets over quadratic number fields, Proc. Roy. Soc. Edinburgh Sect. A 147 (2017), 245–262.

[4] B. E. Brown and D. M. Gordon, On sequences without geometric progressions, Math. Comp. 65 (1996), 1749–1754.

[5] J. Conway and D. Smith, On Quaternions and Octonions: Their Geometry, Arithmetic, and Symmetry, A K Peters/CRC Press, 2003.

[6] N. McNew, On sets of integers which contain no three terms in geometric progression, Math. Comp. 84 (2015), 2893–2910.

[7] M. B. Nathanson and K. O’Bryant, On sequences without geometric progressions, Integers 13 (2013), A73.

[8] I. Negrini, On the computation of p-adic theta functions arising from the Hurwitz quaternions, Master’s thesis, Concordia University, 2017. Available at

https://spectrum.library.concordia.ca/id/eprint/982803/.

[9] R. A. Rankin, Sets of integers containing not more than a given number of terms in arithmetical progression, Proc. Roy. Soc. Edinburgh Sect. A 65 (1961), 332–344.

[10] J. Riddell, Sets of integers containing no n terms in geometric progression, Glasg. Math. J. 10 (1969), 137–146.

[11] N. J. A. Sloane and OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2024. Published electronically at https://oeis.org.

[12] J. Voight, Quaternion Algebras, Springer-Verlag, 2021.

2020 Mathematics Subject Classification: Primary 11B05; Secondary 05D10, 11Y60. Keywords: Ramsey theory, greedy algorithm, non-commutative group, quaternion, Hurwitz quaternion, density, asymptotic density, geometric progression, geometric-progression-free sequence.

(Concerned with sequences \underline{A000452}, \underline{A004011}, and \underline{A005836}.)

Received June 7 2019; revised versions received October 16 2023; January 20 2024; October 14 2024. Published in Journal of Integer Sequences, October 15 2024.

Return to Journal of Integer Sequences home page.