On the convex closure of the graph of modular inversions. (English) Zbl 1234.11005

Summary: We give upper and lower bounds as well as a heuristic estimate on the number of vertices of the convex closure of the set \[ G_n=\{(a,b) : a,b\in \mathbb Z,\; ab \equiv 1\pmod n,\; 1\leq a,b\leq n-1\}. \] The heuristic is based on an asymptotic formula of A. Rényi and R. Sulanke [Z. Wahrscheinlichkeitstheor. Verw. Geb. 2, 75–84 (1963; Zbl 0118.13701)]. After describing two algorithms to determine the convex closure, we compare the numeric results with the heuristic estimate, and find that they do not agree – there are some interesting peculiarities, for which we provide a heuristic explanation. We then describe some numerical work on the convex closure of the graph of random quadratic and cubic polynomials over \(\mathbb Z_n\). In this case the numeric results are in much closer agreement with the heuristic, which strongly suggests that the curve \(xy\equiv 1\pmod n\) is “atypical”.


11A07 Congruences; primitive roots; residue systems
11H06 Lattices and convex bodies (number-theoretic aspects)
11K38 Irregularities of distribution, discrepancy
11N25 Distribution of integers with specified multiplicative constraints


Zbl 0118.13701
Full Text: DOI arXiv Euclid