## 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”.

### MSC:

 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

### Keywords:

modular inversion; convex hull; distribution of divisors

Zbl 0118.13701
Full Text: