Exact formulas using convex geometry

The preceding chapters keep the geometry concrete: residue classes are drawn in the positive lattice window, and the zero class is described both by its divisor envelope and by its exact comparison with the continuous hyperbola $y=N/x$. This chapter does not change the underlying object of study. The set $A_{N,a}$ remains the same finite arithmetic set cut out by a congruence. What changes here is the language. We translate the same finite data into support functions, integrals, and exponential expressions in order to obtain exact but implicit formulas.

The support function

Before introducing the notation, it helps to fix the geometric picture. Choose a direction $\theta$. Now look at all lines perpendicular to that direction and slide one of them across the plane until it just touches the convex hull from the outside. The touching point is a point where the quantity $$x \cos\theta + y \sin\theta$$ is as large as possible. So the support function is simply a record of how far out the set reaches in each direction.

@fig:support-direction-n7-a2 shows this in a concrete case. For the diagonal direction $\theta=\pi/4$, maximizing $x \cos\theta + y \sin\theta$ is the same as maximizing $x+y$, so one sees the supporting line and the winning hull points directly.

$A support line for $A_{7,2}$ at the diagonal direction $\theta=\pi/4$. The dashed line is the outermost line of the form $x+y=\text{constant}$ that still touches the hull, so the highlighted points are exactly the maximizers of the support function in that direction.$

The diagonal directions $\theta=\pm \pi/4$ are also where the support-function viewpoint meets earlier extremal work on modular inverses. For the unit hyperbola $xy \equiv 1 \pmod n$, maximizing $|x-y|$ is exactly the problem of pushing a support line in the $\pm \pi/4$ directions, and Ford, Khan, Shparlinski, and Yankov study the resulting extremal quantity $M(n)=\max\{|a-b|:ab\equiv 1 \pmod n\}$ by analytic and divisor-distribution methods [@fordkhanshparlinskiyankov2005]. Their focus is asymptotic and one-directional: the unit class, one extremal statistic, and upper/lower bounds. The present chapter keeps that same geometric mechanism but asks for the full support function $h_{N,a}(\theta)$ for every residue class and then integrates it into exact area formulas.

For a compact convex set $K \subset \mathbb{R}^2$, its support function is $$h_K(\theta) = \max_{(x,y) \in K} (x \cos\theta + y \sin\theta).$$ Because the maximum of a linear functional does not change when passing from a set to its convex hull, $$h_{\operatorname{conv}(E)}(\theta) = \max_{(x,y) \in E} (x \cos\theta + y \sin\theta)$$ for every finite set $E$.

For the modular set $A_{N,a}$ we therefore define $$h_{N,a}(\theta) := \max_{\substack{1 \leq x, y \leq N-1 \\ xy \equiv a \pmod{N}}} (x \cos\theta + y \sin\theta).$$ This quantity automatically selects points on the convex hull; interior points never maximize a supporting linear functional.

Example (A support direction for $A_{7,2}$). The residue class $$A_{7,2} = \{(1,2), (2,1), (3,3), (4,4), (5,6), (6,5)\}.$$ At the diagonal direction $\theta = \pi/4$, shown in @fig:support-direction-n7-a2, one has $$x\cos\theta + y\sin\theta = \frac{x+y}{\sqrt{2}},$$ so maximizing the support function is the same as maximizing $x+y$. Among the six points above, the largest value is $$x+y = 11,$$ attained at $(5,6)$ and $(6,5)$. Therefore $$h_{7,2}(\pi/4) = \frac{11}{\sqrt{2}}.$$ This simple calculation shows what the support function is really tracking: as the direction rotates, different hull points take turns maximizing the same linear functional.

Remark (A geometric encoding of a finite arithmetic problem). The support function is not a new object replacing $A_{N,a}$; it is an exact Euclidean encoding of the same finite congruence class. The difficulty of the problem remains arithmetic: one must still understand which lattice points become extremal.

Support-function area formula

Once the support function is known in every direction, it encodes the whole convex polygon. A standard fact from convex geometry then turns that directional data into area.

A standard fact from planar convex geometry is the identity $$\operatorname{Area}(K) = \frac{1}{2} \int_0^{2\pi} \bigl(h_K(\theta)^2 - h_K'(\theta)^2\bigr)\, d\theta,$$ valid for polygons and more generally for sufficiently regular convex bodies.

Applying this to $K = \operatorname{conv}(A_{N,a})$ yields the exact formula $$S(N, a) = \frac{1}{2} \int_0^{2\pi} \bigl(h_{N,a}(\theta)^2 - h_{N,a}'(\theta)^2\bigr)\, d\theta. \tag{6.1}$$

On any interval of angles where the same vertex $(x_0,y_0)$ remains the maximizer, the support function is simply $$h_{N,a}(\theta) = x_0\cos\theta + y_0\sin\theta,$$ so on that interval $$h_{N,a}'(\theta) = -x_0\sin\theta + y_0\cos\theta.$$ Thus the derivative records how the same supporting point is seen from nearby directions. The real difficulty in formula (6.1) lies in the switching: one must determine exactly when the maximizing lattice point changes as $\theta$ rotates.

Remark (What formula (6.1) does and does not solve). Formula (6.1) is exact, but it does not yet provide a closed arithmetic formula in $N$ and $a$. The difficult part is hidden in the maximization defining $h_{N,a}(\theta)$: one still needs to know which lattice point wins in each direction $\theta$.

An exponential form

Using the exponential indicator, one may write $$F_{N,a}(\theta, \lambda) := \sum_{x=1}^{N-1} \sum_{y=1}^{N-1} \mathbf{1}_{xy \equiv a \pmod{N}}\, e^{\lambda(x\cos\theta + y\sin\theta)}.$$ Then $$F_{N,a}(\theta, \lambda) = \frac{1}{N} \sum_{r=0}^{N-1} e^{-2\pi i r a / N} \sum_{x=1}^{N-1} \sum_{y=1}^{N-1} \exp\!\left(\frac{2\pi i r x y}{N} + \lambda(x\cos\theta + y\sin\theta)\right).$$

By the log-sum-exp identity, $$h_{N,a}(\theta) = \lim_{\lambda \to \infty} \frac{1}{\lambda} \log F_{N,a}(\theta, \lambda).$$

Substituting this into (6.1) yields a fully analytic representation of $S(N, a)$ in terms of exponentials. This is exact, but it is still implicit. It should be read as an exact filter for finite arithmetic data, not as a replacement for the arithmetic or geometric viewpoints developed in the surrounding chapters.