A370164 The number of residues mod n that occur among the Markov numbers.

1, 2, 2, 2, 5, 4, 4, 3, 6, 10, 8, 4, 13, 8, 10, 5, 17, 12, 16, 10, 8, 16, 20, 6, 25, 26, 18, 8, 29, 20, 28, 9, 16, 34, 20, 12, 37, 32, 26, 15, 41, 16, 40, 16, 30, 40, 44, 10, 28, 50, 34, 26, 53, 36, 40, 12, 32, 58, 56, 20, 61, 56, 24, 18, 65, 32, 64, 34, 40

Offset: 1

Author

Wouter Meeussen and William P. Orrick, Feb 26 2024

Keywords

• nonn

Comments

No Markov number is divisible by any prime congruent to 3 (mod 4). Proof: Let m be a Markov number and let p be an odd prime dividing m. Then there exist positive integers b and c such that m^2 + b^2 + c^2 = 3 * m * b * c (Markov's equation). Furthermore it is known that b and c must be coprime to m. Evaluating Markov's equation (mod p) gives b^2 = -c^2 (mod p), which implies -1 is a square (mod p). This is only possible if p = 1 (mod 4).

Given a prime p congruent to 3 (mod 4) and greater than 3, no Markov number is congruent to 1/3 * (p - 2 * sigma(p)) or 2/3 * (p + sigma(p)) (mod p), where sigma(p) = -1 if p is congruent to 7 (mod 12) and sigma(p) = 1 if p is congruent to 11 (mod 12). Proof: Let m be a Markov number congruent to one of the forbidden residues (mod p). Then evaluating Markov's equation (mod p) using the forms of the forbidden residues above and doing a few simplifications implies that -4 is a square (mod p). This contradicts that p = 3 (mod 4).

The first comment above implies that an odd Markov number is congruent to 1 (mod 4). It has also been shown that any positive even integer satisfying all of the constraints of the first two comments above is congruent to 2 (mod 32).

It is conjectured that, modulo n, all residues not forbidden by the constraints in the three comments above are actually realized by some Markov number. Specifically, mod n the forbidden residues include the following: (1) if p is a prime congruent to 3 (mod 4) that divides n, then any residue congruent to 0 (mod p) or congruent to either of the forbidden residues listed in the second comment (mod p), (2) if 4 divides n, then any odd residue congruent to 3 (mod 4), (3) if 2^r is the highest power of 2 dividing n and 2 <= r <= 5, then any even residue not congruent to 2 (mod 2^r), (4) if 2^r is the highest power of 2 dividing n and r > 5, then any even residue not congruent to 2 (mod 32). It is conjectured that all other residues occur. This has been verified for all n <= 38000.

If the conjecture in the previous comment is correct, then it follows from the Chinese remainder theorem that a(n) may be found by writing n = 2^s * 3^t * u * p_1^r_1 * p_2^r_2 * ... * p_k^r_k, where p_1, ..., p_k are distinct primes greater than 3 and congruent to 3 (mod 4) and r_1, ..., r_k are positive and where the prime divisors of u are all congruent to 1 (mod 4). Then a(n) = u * C_s * D_t * Product_{j=1..k} (p_j - 3) * p_j^(r_j - 1), where C_s = 2^s if s < 2, 1 + 2^(s-2) if 2 <= s <= 5, and 2^(s - 5) + 2^(s - 2) if s > 5, and where D_t = 1 if t = 0 and 2 * 3^(t-1) if t > 0. If the conjecture holds then a(n) is a multiplicative function.

Examples

			If n = 56 = 7 * 8 then, since only the residues 1, 2, 5, 6 are allowed (mod 7) and only the residues 1, 2, 5 are allowed (mod 8), the number of potential residues (mod 56) is 4 * 3 = 12, and these residues are 1, 2, 5, 9, 13, 26, 29, 33, 34, 37, 41, 50. That these residues are realized by Markov numbers is witnessed by 1, 2, 5, 233, 13, 194, 29, 89, 34, 1325, 433, 610.
		

References

• Martin Aigner, Markov's theorem and 100 years of the uniqueness conjecture. A mathematical journey from irrational numbers to perfect matchings. Springer, 2013. x+257 pp. ISBN: 978-3-319-00887-5; 978-3-319-00888-2 MR3098784.

Links

• William P. Orrick, Table of n, a(n) for n = 1..20000
• Martin Aigner, Markov's theorem and 100 years of the uniqueness conjecture. A mathematical journey from irrational numbers to perfect matchings, [archive.org copy of the book].

Crossrefs

Markov numbers: A002559.

Markov tree: A327345, A368546.

Triangle giving list of residues mod n: A370852.

Formula

Conjectured: write n = 2^s * 3^t * u * p_1^r_1 * p_2^r_2 * ... * p_k^r_k, where p_1, ..., p_k are distinct primes greater than 3 and congruent to 3 (mod 4) and r_1, ..., r_k are positive and where the prime divisors of u are all congruent to 1 (mod 4). Then a(n) = u * C_s * D_t * Product_{j=1..k} (p_j - 3) * p_j^(r_j - 1), where C_s = 2^s if s < 2, 1 + 2^(s-2) if 2 <= s <= 5, and 2^(s - 5) + 2^(s - 2) if s > 5, and where D_t = 1 if t = 0 and 2 * 3^(t-1) if t > 0.