Return of the superheroes — Achyuth Jayadevan

Problem

For an odd prime $p$ and $1\le a,b\le n<p$ ,

\begin{aligned} x_0&=0,\\ T_{a,b}(x)&=x^2+ax+b\pmod p,\\ x_{j+1}&=T_{a,b}(x_j),\\ f_p(a,b)&=\min\{j\ge1:x_j\in\{x_0,\ldots,x_{j-1}\}\}. \end{aligned}

\boxed{B(n,p)=\max_{\pi\in S_n}\min_{1\le a\le n}f_p(a,\pi(a))}

B(611,14411),\qquad \max_{2\le n\le999}B(n,17377).

Tail length $\mu$ , cycle length $\lambda$ :

\begin{gathered} x_0\to\cdots\to x_{\mu-1}\to \underbrace{x_\mu\to\cdots\to x_{\mu+\lambda-1}\to x_\mu}_{\lambda\text{-cycle}},\\ f_p(a,b)=\mu+\lambda. \end{gathered}

For $(a,b,p)=(1,3,101)$ ,

\begin{gathered} 0,3,15,41,\underbrace{8,75,47,37,96,23,50,28,7,59}_{\lambda=10},\underline{8},\ldots\\ \mu=4,\qquad \lambda=10,\qquad f_{101}(1,3)=14. \end{gathered}

In $\mathbb F_p$ , put $s=a/2$ , $c=b+s-s^2$ , and $\tau_s(x)=x+s$ . Then

\begin{aligned} \tau_s\circ T_{a,b}\circ\tau_s^{-1}(y)&=y^2+c=:q_c(y),\\ y_0&=s,\\ f_p(a,b)&=\mu_c(s)+\lambda_c(s). \end{aligned}

Memoize $(\mu_c(y),\lambda_c(y))$ per discovered state $(c,y)$ :

\begin{aligned} y\text{ on an }\ell\text{-cycle}:&\quad(\mu_c(y),\lambda_c(y))=(0,\ell),\\ y\text{ off-cycle}:&\quad\mu_c(y)=1+\mu_c(q_c(y)),\\ &\quad\lambda_c(y)=\lambda_c(q_c(y)). \end{aligned}

\begin{aligned} G_t&=([n],[n],E_t),\\ E_t&=\{(a,b):f_p(a,b)\ge t\},\\ B(n,p)\ge t&\iff \nu(G_t)=n,\\ E_{t+1}&\subseteq E_t. \end{aligned}

Here $\nu$ is the maximum matching size. Binary search in $t$ ; Hopcroft–Karp per threshold:

O((|E_t|+n)\sqrt n).

For $(n,p)=(5,101)$ ,

\begin{aligned} \pi&=(3,1,4,2,5),\\ \bigl(f_{101}(a,\pi(a))\bigr)_{a=1}^5&=(14,18,19,22,14),\\ \nu(G_{14})&=5,\qquad \nu(G_{15})=4,\\ B(5,101)&=14. \end{aligned}

Hall’s theorem, with $N_t(S)$ the neighbors of $S$ in $G_t$ :

\nu(G_t)=n\iff\forall S\subseteq[n],\quad |N_t(S)|\ge|S|.

Thus

\begin{gathered} \pi\in S_n,\quad \min_a f_p(a,\pi(a))\ge t\\ \Longrightarrow B(n,p)\ge t,\\[6pt] |N_{t+1}(S)|<|S|\Longrightarrow B(n,p)\le t. \end{gathered}

A singleton obstruction on either side gives

\begin{aligned} B(n,p)&\le\min_a\max_b f_p(a,b),\\ B(n,p)&\le\min_b\max_a f_p(a,b). \end{aligned}

For $p=14411$ , exact computation gives

\begin{aligned} \max_{1\le a\le611}f_p(a,493)&=349,\\ \operatorname*{arg\,max}_{1\le a\le611}f_p(a,493)&=\{402\}. \end{aligned}

The certificate supplies $\pi\in S_{611}$ with

\begin{aligned} \pi(402)&=493,\\ f_p(402,\pi(402))&=349,\\ a\ne402&\Longrightarrow f_p(a,\pi(a))\ge350. \end{aligned}

\boxed{349\le B(611,14411)\le349}

Fix $p=17377$ . Exact maxima:

\begin{aligned} \max_{1\le a\le490}f_p(a,1)&=404,\\ \max_{1\le b\le777}f_p(145,b)&=405,\\ \max_{1\le b\le999}f_p(759,b)&=408,\\ \max_{1\le a\le923}f_p(a,513)&=405. \end{aligned}

Hence

B(n,p)\le \begin{cases} 404,&2\le n\le490,\\ 405,&491\le n\le777,\\ 408,&778\le n\le999, \end{cases}

and

778\le n\le923\Longrightarrow B(n,p)\le405<408.

The certificate supplies a base matching $\pi_{924}$ and augmenting-path updates:

\begin{gathered} \pi_{924}\rightsquigarrow\pi_{925}\rightsquigarrow\cdots\rightsquigarrow\pi_{999},\\ \forall n\in\{924,\ldots,999\},\quad\pi_n\in S_n,\\ \min_{a\le n}f_p(a,\pi_n(a))\ge408. \end{gathered}

\boxed{\max_{2\le n\le999}B(n,17377)=408}

\boxed{\operatorname*{arg\,max}_{2\le n\le999}B(n,17377)=\{924,\ldots,999\}}