TAOCP 3.2.2 Exercise 37
Let $T(x)=a x^{-1}+c \pmod p,$ where the value $\infty$ is adjoined in the usual way: $T(0)=\infty,\qquad T(\infty)=c.$ Since the sequence has period $p+1$, the transformation $T$ acts as a single cyc...
Exercise 37. ▶ [HM32] Let $p$ be prime and assume that $X_{n+1} = (aX_n^{-1} + c) \bmod p$ defines an inversive congruential sequence of period $p + 1$. Also let $0 \le b_1 < \cdots < b_d \le p$, and consider the set
$$V = \bigl{(X_{n+b_1}, X_{n+b_2}, \ldots, X_{n+b_d}) \mid 0 \le n \le p\bigr} \text{ and } X_{n+b_j} \ne \infty \text{ for } 1 \le j \le d\bigr}.$$
This set contains $p + 1 - d$ of which $d$ lie in some $(d-1)$-dimensional hyperplane $H = {(r_1, \ldots, r_d) \mid r_1 v_1 + \cdots + r_d v_d \equiv v_0 \pmod{p}}$, where $(r_1, \ldots, r_d) \ne (0, \ldots, 0)$. Prove that no $d + 1$ vectors of $V$ lie in the same hyperplane.
Verified: yes
Solve time: 1m23s
Setup
Let
$T(x)=a x^{-1}+c \pmod p,$
where the value $\infty$ is adjoined in the usual way:
$T(0)=\infty,\qquad T(\infty)=c.$
Since the sequence has period $p+1$, the transformation $T$ acts as a single cycle on the projective line
$\mathbf P^1(\mathbf F_p)=\mathbf F_p\cup{\infty}.$
Fix integers
$0\le b_1<b_2<\cdots<b_d\le p.$
For each $n$ such that none of
$$$$
equals $\infty$, define
$$$$
The set $V$ contains $p+1-d$ vectors, because during one full cycle each coordinate position $b_j$ contributes exactly one forbidden value $\infty$.
By hypothesis, there is a hyperplane
$$ v_1r_1+\cdots+v_dr_d\equiv v_0\pmod p}, $$
with $(v_1,\ldots,v_d)\neq(0,\ldots,0)$, that contains exactly $d$ points of $V$.
It remains to prove that no hyperplane contains $d+1$ points of $V$.
Solution
Exercise 34 identifies the period-$p+1$ inversive generator with a projective linear transformation. Let
$$ M=\begin{pmatrix} 0&1\ a&c \end{pmatrix}. $$
The hypothesis that the period is $p+1$ implies that the image of $M$ in $\operatorname{PGL}(2,p)$ has order $p+1$.
Choose a point $\alpha\in\mathbf P^1(\mathbf F_p)$ and write
$$ X_n=M^n(\alpha). $$
Let
$$ M^{b_j}= \begin{pmatrix} A_j&B_j\ C_j&D_j \end{pmatrix}. $$
If
$$ x=X_n, $$
then
$$ X_{n+b_j} = \frac{A_jx+B_j}{C_jx+D_j}, $$
whenever the denominator is nonzero.
Suppose a hyperplane
$$ K:\quad v_1r_1+\cdots+v_dr_d\equiv v_0\pmod p $$
contains a point $R_n\in V$. Substituting the above expressions gives
$$ \sum_{j=1}^d v_j\frac{A_jx+B_j}{C_jx+D_j} -v_0 =0. $$
Multiplying by
$$ Q(x)=\prod_{j=1}^d(C_jx+D_j) $$
yields a polynomial equation
$$ F(x)=0, $$
where
$$ F(x)= \Bigl(\sum_{j=1}^d v_j\frac{A_jx+B_j}{C_jx+D_j} -v_0\Bigr)Q(x). $$
Each summand contributes a polynomial of degree at most $d-1$, and the term $-v_0Q(x)$ has degree at most $d$. Hence
$$ \deg F\le d. $$
The matrices $M^{b_1},\ldots,M^{b_d}$ represent distinct projective transformations because
$$ 0\le b_1<\cdots<b_d<p+1 $$
and the order of $M$ in $\operatorname{PGL}(2,p)$ is $p+1$. Therefore the linear fractional functions
$$ \frac{A_jx+B_j}{C_jx+D_j} $$
are distinct.
Assume that $K$ contains $d+1$ vectors of $V$. These vectors correspond to $d+1$ distinct values of $x$, because the orbit of $M$ has length $p+1$.
For each such value of $x$, none of the denominators $C_jx+D_j$ vanishes, since the corresponding vector belongs to $V$. Therefore each of these $d+1$ values is a root of $F(x)$.
Since $\deg F\le d$, a polynomial over $\mathbf F_p$ having $d+1$ distinct roots must be identically zero. Thus
$$ F(x)\equiv0. $$
Dividing by $Q(x)$ in the field of rational functions gives
$$ \sum_{j=1}^d v_j\frac{A_jx+B_j}{C_jx+D_j} \equiv v_0. $$
The poles of the distinct linear fractional functions occur at distinct points. Let $x=-D_t/C_t$ be a pole of the $t$th term. Multiplying the above identity by $(C_tx+D_t)$ and evaluating at that pole gives
$$ v_t(A_tD_t-B_tC_t)=0. $$
Since
$$ A_tD_t-B_tC_t=\det(M^{b_t})=a^{,b_t}\neq0, $$
it follows that
$$ v_t=0. $$
This argument applies to every $t$, hence
$$ v_1=\cdots=v_d=0. $$
Then the identity reduces to
$$ 0\equiv v_0, $$
so the defining equation of $K$ is trivial, contradicting the assumption that
$$ (v_1,\ldots,v_d)\neq(0,\ldots,0). $$
Therefore no hyperplane can contain $d+1$ vectors of $V$.
Verification
For a hyperplane $K$, membership of a vector of $V$ is equivalent to a rational-function equation in one variable $x=X_n$.
After clearing denominators, the resulting polynomial $F(x)$ has degree at most $d$.
If $K$ contained $d+1$ vectors of $V$, then $F(x)$ would have $d+1$ distinct roots, forcing $F\equiv0$.
An identically vanishing linear combination of distinct Möbius transformations is impossible. Examining the residue at the pole of each transformation shows successively that every coefficient $v_j$ must vanish.
This contradicts the definition of a hyperplane.
Hence every hyperplane contains at most $d$ vectors of $V$.
Notes
The argument is the projective analogue of the standard proof that points produced by a maximal-period linear recurrence satisfy no nontrivial affine relation in more than the expected number of positions. The crucial fact is that a nontrivial linear combination of $d$ distinct fractional linear transformations cannot vanish identically, while the hyperplane condition produces a polynomial of degree at most $d$ after denominators are cleared.
This completes the proof.
∎