$\displaystyle\begin{split}\langle
f_{M}(x)-f_{M}(y),x-y\rangle=\int_{y}^{x}f_{M}^{\prime}(r)(x-y)\,\mathrm{d}r\leq-
c_{1}(x-y)^{2}\end{split}$ (222)

which implies monotonicity of the Adam vector field.

###### Proof.

We show that the integrands in the expectations of (220) are uniformly
bounded. By the Cauchy-Schwarz inequality, one has that

$\displaystyle\begin{split}|\mathbb{M}_{M}^{\alpha}(\theta)|&=(1-\alpha)\Bigl{|}\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-k}\beta^{k/2}\beta^{-k/2}\mathbb{X}_{M}({\mathbb{U}}_{k},\theta)\Bigr{|}\\\
&\leq(1-\alpha)\Bigl{(}\sum_{k\in-{\mathbb{N}}_{0}}\alpha^{-2k}\beta^{k}\Bigr{)}^{1/2}\Bigl{(}\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}\mathbb{X}_{M}({\mathbb{U}}_{k},\theta)^{2}\Bigr{)}^{1/2}\\\
&=\frac{1-\alpha}{\sqrt{1-\alpha^{2}/\beta}\sqrt{1-\beta}}\sqrt{\mathbb{V}_{M}(\theta)}\end{split}$
(223)

and by Jensen’s inequality that

$\displaystyle\begin{split}\bigl{|}\mathbb{M}_{M}^{\beta}(\theta)\bigr{|}\leq\Bigl{(}(1-\beta)\sum_{k\in-{\mathbb{N}}_{0}}\beta^{-k}\mathbb{X}_{M}({\mathbb{U}}_{k},\theta)^{2}\Bigr{)}^{1/2}=\sqrt{\mathbb{V}_{M}(\theta)}.\end{split}$
(224)

This implies that

$\displaystyle\begin{split}\Bigl{|}\mathbb{M}^{\alpha}_{M}({\theta})\mathbb{M}^{\beta}_{M}({\theta})\frac{1}{(\sqrt{\mathbb{V}_{M}({\theta})}+\epsilon)^{2}}\frac{1}{\sqrt{\mathbb{V}_{M}({\theta})}}\Bigr{|}\leq\frac{1-\alpha}{\sqrt{1-\alpha^{2}/\beta}\sqrt{1-\beta}}\frac{1}{\sqrt{\mathbb{V}_{M}(\theta)}+\epsilon}.\end{split}$
(225)

Next, take a convergent series $(\vartheta_{M})_{M\in{\mathbb{N}}}$ and denote
by $\vartheta$ its limit. Then for $\rho\in\\{\alpha,\beta\\}$

$\displaystyle\begin{split}\lim_{M\to\infty}\mathbb{M}^{\rho}_{M}(\vartheta_{M})={\mathbb{E}}[U]-\vartheta,\text{
\ in probability,}\end{split}$ (226)

and

$\displaystyle\begin{split}\lim_{M\to\infty}\mathbb{V}_{M}(\vartheta_{M})=({\mathbb{E}}[U]-\vartheta)^{2},\text{
\ in probability.}\end{split}$ (227)

This entails that, in probability,

$\displaystyle\begin{split}\lim_{M\to\infty}\frac{1}{\sqrt{\mathbb{V}_{M}(\vartheta_{M})}+\epsilon}=\frac{1}{|{\mathbb{E}}[U]-\vartheta|+\epsilon}\end{split}$
(228)

and

$\displaystyle\begin{split}\lim_{M\to\infty}\mathbb{M}^{\alpha}_{M}({\vartheta_{M}})\mathbb{M}^{\beta}_{M}({\vartheta_{M}})\frac{1}{(\sqrt{\mathbb{V}_{M}({\vartheta_{M}})}+\epsilon)^{2}}\frac{1}{\sqrt{\mathbb{V}_{M}({\vartheta_{M}})}}=\frac{|{\mathbb{E}}[U]-\vartheta|}{(|{\mathbb{E}}[U]-\vartheta|+\epsilon)^{2}}.\end{split}$
(229)

With dominated convergence, we thus get that

$\displaystyle\begin{split}\lim_{M\to\infty}f^{\prime}_{M}(\vartheta_{M})=-\frac{1}{|{\mathbb{E}}[U]-\vartheta|+\epsilon}\Bigl{(}1-\frac{|{\mathbb{E}}[U]-\vartheta|}{|{\mathbb{E}}[U]-\vartheta|+\epsilon}\Bigr{)}<0.\end{split}$
(230)

We prove the statement by contradiction. If the statement would not be true
for every choice of $M_{0}$ there would exist a sequence
$(M_{k})_{k\in{\mathbb{N}}}$ of integers diverging to infinity and a
$V$-valued sequence $(\vartheta_{k})_{k\in{\mathbb{N}}}$ with

$\displaystyle\begin{split}\limsup_{k\to\infty}f^{\prime}_{M_{k}}(\vartheta_{k})\geq
0.\end{split}$ (231)

By compactness of $V$, we can assume that $(\vartheta_{k})$ is convergent with
a limit $\theta\in V$ (if the sequence is not convergent, we can instead work
with a convergent subsequence). This contradicts our computations above, see
(230). ∎

######  Lemma 9.2.

There exists $M_{0}\in{\mathbb{N}}$ and $\kappa\in(0,\infty)$ such that for
every $M\in{\mathbb{N}}$ with $M\geq M_{0}$ there exists
$\vartheta_{M}\in{\mathbb{R}}$ with $|\vartheta_{M}-{\mathbb{E}}[U]|\leq\kappa
M^{-1}$ and $f_{M}(\vartheta_{M})=0$.

###### Proof.

Set $u={\mathbb{E}}[U]$. Without loss of generality we can assume that $U$ has
a strictly-positive variance. (Otherwise, $f_{M}(u)=0$ and we can choose
$\vartheta_{M}=u$.) To apply Theorem 8.3 we need estimates for
${\mathbb{E}}[|h^{\prime}(\mathbbm{V}_{M})|]$ and
${\mathbb{E}}[h^{\prime\prime}(\mathbbm{V}_{M})]$.

Pick $q\in(0,\beta^{3/2})$. The classical central limit theorem implies that

$\displaystyle\begin{split}\sqrt{M}\,\mathbb{X}_{M}({\mathbb{U}},\theta)\Rightarrow\mathcal{N}(0,\mathrm{Var}(U))\end{split}$
(232)

as $M\to\infty$. Thus we can choose $M_{0}^{\prime}\in{\mathbb{N}}$ and
$\delta^{\prime}\in(0,\infty)$ so that for all $M\in{\mathbb{N}}$ with $M\geq
M_{0}^{\prime}$ one has

$\displaystyle\begin{split}{\mathbb{P}}(|\sqrt{M}\,X_{M}(U,\theta)|<\sqrt{\delta^{\prime}})\leq
q\text{ \ or, equivalently, \
}{\mathbb{P}}(X_{M}(U,\theta)^{2}<{\delta^{\prime}}/M)\leq q.\end{split}$
(233)

With Lemma 8.5 we thus obtain that for $p\in\\{1/2,3/2\\}$

$\displaystyle\begin{split}{\mathbb{E}}[\mathbb{V}_{M}^{-p}]\leq\Bigl{(}\frac{\beta}{1-\beta}\Bigr{)}^{p}\frac{1-q}{\beta^{p}-q}(M/\delta^{\prime})^{p}.\end{split}$
(234)

In particular, the latter expectations are finite and we are now in the
position to apply Theorem 8.3: there exists a constant $\kappa_{1}$ only
depending on $\alpha$, $\beta$ and the first five moments of $U$ so that for
every $M\in{\mathbb{N}}$ with $M\geq M_{0}^{\prime}$ one has that

$\displaystyle\begin{split}|f_{M}(u)|\leq\kappa_{1}\bigl{(}{\mathbb{E}}[|h^{\prime}(\mathbb{V}_{M})|]\,M^{-2}+{\mathbb{E}}[h^{\prime\prime}(\mathbb{V}_{M})]\,M^{-5/2}\bigr{)}.\end{split}$
(235)

Note that for all $x\in(0,\infty)$, $|h^{\prime}(x)|\leq\epsilon^{-2}x^{-1/2}$
and $h^{\prime\prime}(x)\leq\epsilon^{-2}x^{-3/2}$ so that

$\displaystyle\begin{split}|f_{M}(u)|\leq\kappa_{1}\epsilon^{-2}\bigl{(}{\mathbb{E}}[\mathbb{V}_{M}^{-1/2}]\,M^{-2}+{\mathbb{E}}[\mathbb{V}_{M}^{-3/2}]\,M^{-5/2}\bigr{)}.\end{split}$
(236)

In view of (234) we get that

$\displaystyle\begin{split}|f_{M}(u)|\leq\kappa_{2}\,M^{-1},\end{split}$ (237)

where $\kappa_{2}$ is a constant only depending on
$\alpha,\beta,\epsilon,\delta^{\prime}$ and $q$ and the first five moments of
$U$.

By Lemma 9.1, we can choose $M_{0}^{\prime\prime}\in{\mathbb{N}}$ such that

$\displaystyle\begin{split}-r:=\sup\\{f^{\prime}_{M}(x):x\in[u-1,u+1]\text{
and }M\geq M_{0}^{\prime\prime}\\}<0.\end{split}$ (238)

Now choose $M_{0}=\max\\{M_{0}^{\prime},M_{0}^{\prime\prime},\kappa_{2}/r\\}$
and note that for $M\in{\mathbb{N}}$ with $M\geq M_{0}$ one has

$\displaystyle\begin{split}f_{M}(u+\mbox{$\frac{\kappa_{2}}{r}$}M^{-1})\leq|f_{M}(u)|-r\mbox{$\frac{\kappa_{2}}{r}$}M^{-1}\leq
0\end{split}$ (239)

and

$\displaystyle\begin{split}f_{M}(u-\mbox{$\frac{\kappa_{2}}{r}$}M^{-1})\geq-|f_{M}(u)|+r\mbox{$\frac{\kappa_{2}}{r}$}M^{-1}\geq
0.\end{split}$ (240)

By the intermediate value theorem, there exists
$\vartheta_{M}\in[u-\mbox{$\frac{\kappa_{2}}{r}$}M^{-1},u+\mbox{$\frac{\kappa_{2}}{r}$}M^{-1}]$
with $f_{M}(\vartheta_{M})=0$. ∎

###### Proof of Theorem 1.1.

Recall that by assumption, the random variable $U$ is uniformly bounded, say
by $C_{1}\in(0,\infty)$. By [5, Corollary 2.5] there exists a constant $C_{2}$
such that for every $M\in{\mathbb{N}}$, the respective Adam algorithm
$(\theta_{n}^{[M]})$ satisfies for all $n\in{\mathbb{N}}_{0}$

$\displaystyle\begin{split}|\theta^{[M]}_{n}|\leq C_{2}.\end{split}$ (241)

This entails that
$X_{n}^{[M]}:=\mathbb{X}_{M}({\mathbb{U}}_{n},\theta^{[M]}_{n-1})$
$(n\in{\mathbb{N}})$ is bounded by $C_{1}+C_{2}$ so that for
$\mathbf{X}^{[M]}_{n}=(1\mathrm{l}_{\\{n+k>0\\}}X_{n+k}^{[M]})_{k\in-{\mathbb{N}}_{0}}$
one has that
$\|\mathbf{X}^{[M]}_{n}\|_{\ell_{\varrho}}\leq(C_{1}+C_{2})\|\varrho\|_{\ell_{1}}$.

By Lemmas 9.1 and 9.2, there exists $M_{0}\in{\mathbb{N}}$,
$\kappa\in(0,\infty)$ and a ${\mathbb{R}}$-valued sequence
$(\vartheta_{M})_{M\geq M_{0}}$ such that $f_{M}(\vartheta_{M})=0$,
$|\vartheta_{M}-{\mathbb{E}}[U]|\leq(\kappa M^{-1})\wedge C_{2}$ and

$\displaystyle\begin{split}-c_{1}:=\sup\bigl{\\{}f_{M}^{\prime}(\theta):M\geq
M_{0},\theta\in[-C_{2},C_{2}]\bigr{\\}}<0.\end{split}$ (242)

This entails that for every $\theta\in[-C,C]$,

$\displaystyle\begin{split}(f_{M}(\theta)-f_{M}(\vartheta_{M}))(\theta-\vartheta_{M})\leq-
c_{1}\,(\theta-\vartheta_{M})^{2}.\end{split}$ (243)

We will apply Theorem 2.5 with $\alpha,\beta,\epsilon$ and $(\gamma_{n})$ as
in the statement of Theorem 1.1. Moreover, let $c_{1}$ as above, $c_{2}=0$,
$p\in(2,\infty)$, $c=c_{1}/2$, $\varepsilon=1$ and
$\mathcal{K}=C_{1}+C_{2}+1$.

We choose $\mathfrak{n}\in{\mathbb{N}}_{0}$ and $\eta\in(0,\infty)$ with
$\sqrt{\gamma_{\mathfrak{n}+1}}\,(C_{1}+C_{2})\|\varrho\|_{\ell_{1}}\leq 1$ so
that the statement in Theorem 2.5 is true for the chosen set of parameters.
Fix $M\in{\mathbb{N}}$ with $M\geq M_{0}$ and let for $\zeta\in{\mathbb{R}}$,
$m\in{\mathbb{R}}$ and $\nu\in[0,\infty)$,
$\theta^{[\zeta,\mathfrak{n},m,\nu]}=(\theta_{n}^{[M,\zeta,\mathfrak{n},m,\nu]})_{n\geq\mathfrak{n}}$
denote the Adam algorithm with innovation $(\mathbb{X}_{M},{\mathbb{U}})$
started at time $\mathfrak{n}$ in $(\zeta,m,\nu)$. Next, we will verify
assumptions 1.-4. for appropriate $M$-dependent Adam algorithms with $M\geq
M_{0}$. Fix $M\geq M_{0}$ and $V=[-C_{2},C_{2}]$.

1.) We have for every $\theta\in V$ that

$\displaystyle\begin{split}{\mathbb{E}}[|\mathbb{X}_{M}({\mathbb{U}},\theta)|^{p}]^{1/p}\leq
C_{1}+C_{2}\leq{\mathcal{K}}\text{ \ and \
}{\mathbb{E}}[|\mathbb{X}_{M}({\mathbb{U}},\theta)-\mathbb{X}_{M}({\mathbb{U}},\theta^{\prime})|^{p}]^{1/p}=|\theta-\theta^{\prime}|\leq{\mathcal{K}}|\theta-\theta^{\prime}|.\end{split}$
(244)

2.) Note that for the random terms $m_{\mathfrak{n}}$ and $v_{\mathfrak{n}}$
one has

$\displaystyle\begin{split}\sqrt{\gamma_{\mathfrak{n}+1}}\,(m_{\mathfrak{n}},v_{\mathfrak{n}})_{\ell_{\varrho}}\leq\sqrt{\gamma_{\mathfrak{n}+1}}\,\|\mathbf{X}^{[M]}({\mathfrak{n}})\|_{\ell_{\varrho}}\leq\sqrt{\gamma_{\mathfrak{n}+1}}\,(C_{1}+C_{2})\|\varrho\|_{\ell_{1}}\leq
1\leq{\mathcal{K}}.\end{split}$ (245)

3.) We choose $\Psi_{M}:[t_{n_{0}},\infty)\to{\mathbb{R}}$ as constant
function $\Psi^{M}\equiv\vartheta_{M}$ and note that it solves the ODE
$\dot{\Psi}^{M}_{t}=0=f_{M}(\Psi^{M}_{t})$.

4.) Choose $\mathfrak{R}_{t}\equiv\infty$ and note that for every $x\in V$,
$(f(x)-f(\Psi_{t}^{M}))(x-\Psi_{t}^{M})\leq-c_{1}\,|x-\Psi^{M}_{t}|^{2}$ is
just property (243) above.

We conclude that for $n\geq\mathfrak{n}$

$\displaystyle\begin{split}{\mathbb{E}}[|\theta_{n}^{[M]}-\vartheta_{M}|^{p}]^{1/p}&={\mathbb{E}}[{\mathbb{E}}[|\theta^{[M]}_{n}-\vartheta_{M}|^{p}|\mathcal{F}_{\mathfrak{n}}]]\\\
&={\mathbb{E}}\Bigl{[}{\mathbb{E}}\bigl{[}\theta_{n}^{[M,\zeta,\mathfrak{n},m,\nu]}-\vartheta_{M}|^{p}\bigr{]}\Big{|}_{(\zeta,m,\nu)=(\theta_{\mathfrak{n}},m_{n_{0}},v_{n_{0}})}\Bigr{]}^{1/p}\\\
&\leq{\mathbb{E}}\Bigl{[}\Bigl{(}\eta+\Bigl{(}(1+\varepsilon)\frac{|\theta_{\mathfrak{n}}-\Psi_{t_{n_{0}}}|}{\sqrt{\gamma_{\mathfrak{n}+1}}}+\eta\sqrt{(m_{\mathfrak{n}},v_{\mathfrak{n}})_{\ell_{\varrho}}}\Bigr{)}e^{-c(t_{n}-t_{\mathfrak{n}})}\Bigr{)}^{p}\Bigr{]}^{1/p}\sqrt{\gamma_{n+1}}\\\
&\leq(\eta+(4C_{2}\gamma_{\mathfrak{n}+1}^{-1/2}]+\eta)e^{-c(t_{n}-t_{\mathfrak{n}})})\sqrt{\gamma_{n+1}}.\end{split}$
(246)

Moreover, ${\mathbb{E}}[|\theta_{n}^{[M]}-\vartheta|^{p}]^{1/p}\leq 2C_{2}$
for all $n\in{\mathbb{N}}$. The latter two bounds do not depend on the choice
of $M$ which proves estimate (b) for an appropriately chosen $\eta$.

To prove (a) we choose $p\in(2,\infty)$ with
$\sum_{n\in{\mathbb{N}}_{0}}\gamma_{n}^{p/2}<\infty$. Using property (b) (with
the respective $\eta$) we conclude that

$\displaystyle\begin{split}{\mathbb{E}}\Bigl{[}\sum_{n\in{\mathbb{N}}_{0}}|\theta_{n}^{[M]}-\vartheta_{M}|^{p}\Bigr{]}\leq\eta^{p}\sum_{n\in{\mathbb{N}}_{0}}\gamma_{n}^{p/2}<\infty\end{split}$
(247)

which implies that, almost surely,
$\sum_{n\in{\mathbb{N}}_{0}}|\theta_{n}^{[M]}-\vartheta_{M}|^{p}<\infty$ and
that $(\theta^{[M]}_{n})$ tends to $\vartheta_{M}$, almost surely. ∎

### Acknowledgements

Shokhrukh Ibragimov is gratefully acknowledged for having brought useful
related research findings to our attention. This work has been partially
funded by the European Union (ERC, MONTECARLO, 101045811). The views and the
opinions expressed in this work are however those of the authors only and do
not necessarily reflect those of the European Union or the European Research
Council (ERC). Neither the European Union nor the granting authority can be
held responsible for them. In addition, this work has been partially funded by
the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under
Germany’s Excellence Strategy EXC 2044–390685587, Mathematics Münster:
Dynamics–Geometry–Structure.

## References

  * [1] Barakat, A., and Bianchi, P. Convergence and dynamical behavior of the Adam algorithm for nonconvex stochastic optimization.  SIAM J. Optim. 31, 1 (2021), 244–274.
  * [2] Chen, X., Liu, S., Sun, R., and Hong, M. On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization.  arXiv:1808.02941 (2024).
  * [3] Cheridito, P., Jentzen, A., and Rossmannek, F. Non-convergence of stochastic gradient descent in the training of deep neural networks.  Journal of Complexity 64 (2021), 101540.
  * [4] Défossez, A., Bottou, L., Bach, F., and Usunier, N. A Simple Convergence Proof of Adam and Adagrad.  Transactions on Machine Learning Research (2022).
  * [5] Dereich, S., Graeber, R., and Jentzen, A. Non-convergence of Adam and other adaptive stochastic gradient descent optimization methods for non-vanishing learning rates.  arXiv:2407.08100 (2024).
  * [6] Dereich, S., Jentzen, A., and Riekert, A. Learning rate adaptive stochastic gradient descent optimization methods: numerical simulations for deep learning methods for partial differential equations and convergence analyses.  arXiv:2406.14340 (2024).
  * [7] Dereich, S., and Kassing, S. Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes.  arXiv:2102.09385 (2021).
  * [8] Ding, K., Xiao, N., and Toh, K.-C. Adam-family Methods with Decoupled Weight Decay in Deep Learning.  arXiv:2310.08858 (2023).
  * [9] Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization.  J. Mach. Learn. Res. 12 (2011), 2121–2159.
  * [10] E, W., Ma, C., Wojtowytsch, S., and Wu, L. Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don’t.  arXiv:2009.10713 (2020).
  * [11] Gallon, D., Jentzen, A., and Lindner, F. Blow up phenomena for gradient descent optimization methods in the training of artificial neural networks.  arXiv:2211.15641 (2022).
  * [12] Gentile, R., and Welper, G. Approximation results for gradient descent trained shallow neural networks in 1d.  arXiv:2209.08399 (2022).
  * [13] Godichon-Baggioni, A., and Tarrago, P. Non asymptotic analysis of Adaptive stochastic gradient algorithms and applications.  arXiv:2303.01370 (2023).
  * [14] He, M., Liang, Y., Liu, J., and Xu, D. Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case.  arXiv:2307.11782 (2023).
  * [15] Hinton, G., Srivastava, N., and Swersky, K. Lecture 6e: Rmsprop: Divide the gradient by a running average of its recent magnitude.  https://www.cs.toronto.edu/~tijmen/csc321/slides/lecture_slides_lec6.pdf.  [Accessed 01-December-2017].
  * [16] Hong, Y., and Lin, J. Revisiting Convergence of AdaGrad with Relaxed Assumptions.  arXiv:2402.13794 (2024).
  * [17] Hu, X., Xiao, N., Liu, X., and Toh, K.-C. Learning-rate-free Momentum SGD with Reshuffling Converges in Nonsmooth Nonconvex Optimization.  arXiv:2406.18287 (2024).
  * [18] Ibragimov, S., Jentzen, A., and Riekert, A. Convergence to good non-optimal critical points in the training of neural networks: Gradient descent optimization with one random initialization overcomes all bad non-global local minima with high probability.  arXiv:2212.13111 (2022).
  * [19] Jentzen, A., Kuckuck, B., Neufeld, A., and von Wurstemberger, P. Strong error analysis for stochastic gradient descent optimization algorithms.  IMA J. Numer. Anal. 41, 1 (2021), 455–492.
  * [20] Jentzen, A., Kuckuck, B., and von Wurstemberger, P. Mathematical Introduction to Deep Learning: Methods, Implementations, and Theory.  arXiv:2310.20360 (2023).
  * [21] Jentzen, A., and Riekert, A. Non-convergence to global minimizers for Adam and stochastic gradient descent optimization and constructions of local minimizers in the training of artificial neural networks.  arXiv:2402.05155 (2024).
  * [22] Kingma, D. P., and Ba, J. Adam: A Method for Stochastic Optimization.  arXiv:1412.6980 (2024).
  * [23] Li, H., Rakhlin, A., and Jadbabaie, A. Convergence of Adam Under Relaxed Assumptions.  arXiv:2304.13972 (2023).
  * [24] Lu, L. Dying ReLU and Initialization: Theory and Numerical Examples.  Communications in Computational Physics 28, 5 (June 2020), 1671–1706.
  * [25] Nesterov, Y. A method of solving a convex programming problem with convergence rate $o(1/k^{2})$.  In Soviet Mathematics Doklady (1983), vol. 27, pp. 372–376.
  * [26] Petersen, P., Raslan, M., and Voigtlaender, F. Topological properties of the set of functions generated by neural networks of fixed size.  Found. Comput. Math. 21, 2 (2021), 375–444.
  * [27] Polyak, B. T. Some methods of speeding up the convergence of iteration methods.  USSR Computational Mathematics and Mathematical Physics 4, 5 (1964), 1–17.
  * [28] Reddi, S. J., Kale, S., and Kumar, S. On the Convergence of Adam and Beyond.  arXiv:1904.09237 (2019).
  * [29] Ruder, S. An overview of gradient descent optimization algorithms.  arXiv:1609.04747 (2017).
  * [30] Sun, R. Optimization for deep learning: theory and algorithms.  arXiv:1912.08957 (2019).
  * [31] Sutskever, I., Martens, J., Dahl, G., and Hinton, G. On the importance of initialization and momentum in deep learning.  In Proceedings of the 30th International Conference on Machine Learning (2013), S. Dasgupta and D. McAllester, Eds., vol. 28 of Proceedings of Machine Learning Research, PMLR, pp. 1139–1147.
  * [32] Welper, G. Approximation Results for Gradient Descent trained Neural Networks.  arXiv:2309.04860 (2023).
  * [33] Welper, G. Approximation and Gradient Descent Training with Neural Networks.  arXiv:2405.11696 (2024).
  * [34] Xiao, N., Hu, X., Liu, X., and Toh, K.-C. Adam-family methods for nonsmooth optimization with convergence guarantees.  J. Mach. Learn. Res. 25 (2024), Paper No. [48], 53.
  * [35] Zeiler, M. D. Adadelta: An adaptive learning rate method.  arXiv:1212.5701 (2012).
  * [36] Zhang, Y., Chen, C., Shi, N., Sun, R., and Luo, Z.-Q. Adam Can Converge Without Any Modification On Update Rules.  arXiv:2208.09632 (2022).
  * [37] Zou, F., Shen, L., Jie, Z., Zhang, W., and Liu, W. A Sufficient Condition for Convergences of Adam and RMSProp.  arXiv:1811.09358 (2018).


# Demicaps in AG(4,3) and Their Relation to Maximal Cap Partitions

Jordan Awan  Dept. of Statistics, Purdue University  ,  Claire Frechette
Mathematics Dept., University of Minnesota Twin Cities  ,  Yumi Li  Willamette
University  and  Elizabeth McMahon  Mathematics Dept., Lafayette College,
Easton, PA<EMAIL_ADDRESS>
###### Abstract.

In this paper, we introduce a fundamental substructure of maximal caps in the
affine geometry $AG(4,3)$ that we call _demicaps_. Demicaps provide a direct
link to particular partitions of $AG(4,3)$ into 4 maximal caps plus a single
point. The full collection of 36 maximal caps that are in exactly one
partition with a given cap $C$ can be expressed as unions of two disjoint
demicaps taken from a set of 12 demicaps; these 12 can also be found using
demicaps in $C$. The action of the affine group on these 36 maximal caps
includes actions related to the outer automorphisms of $S_{6}$.

###### Key words and phrases:

Finite affine geometry, maximal caps, affine transformations, outer
automorphisms of $S_{6}$. MSC: 51E15, 51E22

Research supported by NSF grant DMS-1063070.

##  1\. Introduction

We introduce a new structure called a demicap in $AG(4,3)$, which is an
extremely well-studied finite geometry. A demicap is a 10-point configuration
that is a fundamental building block for the maximal caps in the geometry. In
addition, demicaps provide a direct link to partitions of $AG(4,3)$ into
disjoint maximal caps plus a distinguished point. Thus, demicaps provide
valuable information about maximal caps and partitions.

$AG(4,3)$ can be partitioned into 4 disjoint maximal caps plus a distinguished
point. Those partitions are in two equivalence classes under affine
transformations. One of those classes contains two pairs of maximal caps that
appear in only one partition. These are the partitions we focus on in this
paper. If $C$ is a maximal cap, then there are exactly 36 maximal caps
disjoint from $C$ that appear in exactly one partition with $C$, and demicaps
can be used to find these 36 caps. Further, any transformation of $AG(4,3)$
that fixes $C$ as a set necessarily permutes the 36 maximal caps, and those
permutations act in the same way as an outer autmorphism of $S_{6}$.

The problem of determining the size and structure of maximal caps in $AG(n,3)$
has received a good deal of attention from many researchers. Many
mathematicians are very interested in the “cap-set problem,” the problem of
finding bounds on the size of the maximal caps in $AG(n,3)$. In 2016, new
upper bounds on the size of such sets were found by Ellenberg and Gijswijt
[5]. A more complete understanding of the geometric structure of maximal caps
could have implications for cap size calculations in other dimensions. The
structures we introduce and examine in this paper could assist with this
project.

We now define the basic structures we will be examining in this paper. A cap
in the affine geometry $AG(n,3)$ is a set of points containing no lines; a
maximal cap is a cap of largest possible size. A cap is complete if it is not
a subset of a larger cap. There are caps in $AG(n,3),\,n\geq 3$, which are
complete but not maximal.

The finite geometry $AG(n,3)$ is an $n$-dimensional vector space over
$\mathbb{Z}_{3}$; three points are on a line if and only if the corresponding
vectors sum to $\vec{0}$. The full transformation group of $AG(n,3)$ is the
affine group $\mathit{Aff}(n,3)=GL(n,3)\ltimes\mathbb{Z}_{3}^{n}$, where
$(A,\vec{b})$ in the semidirect product corresponds to the transformation
$\vec{v}\mapsto A\vec{v}+\vec{b}$.

All maximal caps in the geometry $AG(4,3)$ have 20 points (G. Pellegrino,
[10]), and all are affinely equivalent (R. Hill, [7]). Each maximal cap $C$ in
$AG(4,3)$ has a unique anchor point $a$, where the 20 points of $C$ consist of
10 pairs of points, so that each pair makes a line with $a$.

Partitions of affine and projective space into caps have been examined by
several researchers (see, for example, [2] and [9]). In this paper, we will
focus on partitions of $AG(4,3)$ into four disjoint maximal caps together with
their common anchor point, which were first explored in [6]. This gives a
partition of $AG(4,3)$ into five caps, the smallest number possible; these
particular partitions also have the largest possible number of maximal caps.

In [6], it was shown that any pair of disjoint maximal caps in $AG(4,3)$ must
necessarily have the same anchor point; a pair of disjoint maximal caps appear
as blocks in either 1, 2 or 6 distinct partitions, so such pairs are called
1-completable, 2-completable, or 6-completable pairs, respectively. The affine
group $\mathit{Aff}(4,3)$ acts transitively on 1-completable pairs,
transitively on 2-completable pairs and transitively on 6-completable pairs.
In this paper, we concentrate on 1-completeable pairs.

Any maximal cap $C$ has exactly 36 maximal caps disjoint from $C$ that appear
with $C$ in precisely one partition of $AG(4,3)$. Additionally, $C$ can be
written as the union of two disjoint demicaps in 36 ways. We show that these
two sets are connected by a bijection. Not only are the demicap partitions of
a maximal cap $C$ related to the maximal caps in exactly one partition with
$C$, but one can also use the demicaps to find the other pair of maximal caps
in the partition.

The structure and number of demicaps is explored in Section 3. In Section 4,
we give the correspondence between a pair of demicaps whose union is $C$ and
one maximal cap $C^{\prime}$ making a 1-completable pair with $C$. We then use
the same pair of demicaps to determine the other two maximal caps in the
partition containing $C$ and $C^{\prime}$.

In Section 5, we show that there are two collections of six demicaps
$\\{R_{1},\dots,R_{6}\\}$ and $\\{C_{1},\dots,C_{6}\\}$ so that every one of
the 36 maximal caps in a unique partition with $C$ is $R_{i}\cup C_{j}$ for
some $i,j\leq 6$. These demicaps can be found from any pair of disjoint
demicaps whose union is $C$. We finish with an exploration of the full set of
36 maximal caps that are in exactly one partition with a maximal cap $C$. The
subgroup of the affine group that fixes $C$ acts on the set of 36 caps as the
full automorphism group of $S_{6}$, including outer automorphism actions.

Thus, what we will show in this paper is that a demicap, a natural
substructure of a maximal cap in $AG(4,3)$, encodes all the information
necessary to find one of the 36 maximal caps that are in exactly one partition
with that cap, as well as a way to identify the other two maximal caps in that
partition. This provides a full accounting of the partitions of $AG(4,3)$
consisting of two 1-completable pairs of maximal caps.

##  2\. Partitions of $AG(4,3)$ into disjoint maximal caps plus their common
anchor point

Throughout our exposition, we will use lower case letters, $a$, for points in
$AG(4,3)$. Occasionally, we will want to consider those points as vectors in
$GF(3)^{4}$, in which case we will write the point with vector notation, as
$\vec{a}$.

Using the same visualization scheme as is used by Davis and Maclagan
[3],111The lines in a $3\times 3$ subgrid are three points horizontally,
vertically, or diagonally, including diagonals as on a torus; the points in
all other lines appear in three subgrids that are in the same position as a
line in the $3\times 3$ subgrids, so that, when the three subgrids are
superimposed, those points either lie on top of one another, or they are in
the same positions as a line in a subgrid. See Figure 1. one maximal cap of
$AG(4,3)$ is shown below in Figure 1. (This is the first maximal cap with
anchor point $\vec{0}$ in the lexicographic order.) The anchor point is in the
upper left corresponding to $\vec{0}$; it is easily verified that the cap
consists of 10 lines through $\vec{0}$.

Figure 1. A maximal cap in $AG(4,3)$ with anchor point in the upper left.

In [6], it was shown that $AG(4,3)$ can be partitioned into four disjoint
maximal caps together with their common anchor point. One such partition is
shown in Figure 2. Any two maximal caps with different anchor points
necessarily intersect (Prop. 3.4, [6]), so all maximal caps in such a
partition have the same anchor point, the blank box in the upper left.

Figure 2. A partition of $AG(4,3)$ into 4 maximal caps plus their associated
anchor point.

Now, we will give further results from [6] that will be needed for this paper.
The terminology used is given in the following definition.

######  Definition.

Given a pair of disjoint maximal caps $C$ and $C^{\prime}$ (necessarily with
the same anchor point), if $C$ and $C^{\prime}$ are in exactly $k$ partitions,
then we call $\\{C,C^{\prime}\\}$ a $k$-completable pair.

The next proposition shows that the only possible values of $k$ for which two
maximal caps are a $k$-completable pair are $k=1,2,6$. it also gives further
information about the structure of the partitions.

######  Proposition 2.1 (Prop. 3.5, Prop. 3.6, Thm. 3.8, [6]).

Let $C$ be a maximal cap with anchor point $a$; let $\mathcal{T}$ be the group
of linear transformations of $AG(4,3)$ that fix $C$ as a set, and let
$T\in\mathcal{T}$.

(1) There are 198 maximal caps disjoint from $C$; every one of those together
with $C$ can be extended to a partition of $AG(4,3)$ into four maximal caps
plus the common anchor point. Of those 198 maximal caps, 36 make a
1-completable pair with $C$; 90 make a 2-completable pair with $C$; and 72
make a 6-completable pair with $C$.

(2) If $\\{C,C^{\prime}\\}$ is an $i$-completable pair for $i=1,2,6$, then so
is $\\{T(C),T(C)^{\prime}\\}$.

(3) Let $\\{\\{a\\},A,B,C,D\\}$ be a partition of $AG(4,3)$ into 4 mutually
disjoint maximal caps together with their anchor point. Then the maximal caps
can be paired so that exactly one of two possibilities holds:

  * •

$\\{A,B\\}$ and $\\{C,D\\}$ are both 1-completable pairs.

  * •

$\\{A,B\\}$ and $\\{C,D\\}$ are both 2-completable pairs.

In both cases, $\\{A,C\\}$, $\\{A,D\\}$, $\\{B,C\\}$, and $\\{B,D\\}$ are
6-completable pairs.

(4) A 6-completable pair $\\{C,C^{\prime}\\}$ appears in exactly one partition
with two 1-completable pairs and in five partitions with two 2-completable
pairs.

(5) The affine group $\mathit{Aff}(4,3)$ acts on the set of partitions of
$AG(4,3)$ into 4 mutually disjoint maximal caps and the associated anchor
point $a$. There are two orbits under that action: one orbit consists of
partitions with two 1-completable pairs, and the other consists of partitions
with two 2-completable pairs.

Our goal in this paper is to understand what distinguishes the first of these
two orbits geometrically.

##  3\. Maximal caps in $AG(4,3)$ and demicaps

Let $C$ be a maximal cap in $AG(n,3)$. Any point not in $C$ must complete a
line with a pair of points from $C$, or $C$ would not be maximal. How many
such lines can a given point complete? The following proposition answers this
question for $AG(n,3)$, $n\leq 6$. (Since our focus is on $AG(4,3)$, that
result is stated first.) .

######  Proposition 3.1.

A maximal cap $C$ in $AG(4,3)$ consists of 10 pairs of points, each of which
completes a line with the anchor point. Any point in $AG(4,3)$ other than the
anchor point and the points in $C$ completes exactly three lines with pairs of
points in $C$.

In $AG(n,3)$, for all other $n$ where the size of a maximal cap is known, a
similar result holds. See Table 1.

Table 1. Known sizes of maximal caps and the number of lines completed by non-anchor points not in the cap. Space | Maximal | Anchor? | Number of lines every non-
---|---|---|---
| cap size |  | anchor point completes
$AG(2,3)$ | 4 | Yes | 1
$AG(3,3)$ | 9 | No | 2
$AG(4,3)$ | 20 | Yes | 3
$AG(5,3)$ | 45 | No | 5
$AG(6,3)$ | 112 | Yes | 10

###### Proof.

The result in all cases can be shown by examining one maximal cap, since all
maximal caps are affinely equivalent in every dimension where the size is
known ([7], [4], [11]), and incidence structures are preserved by affine
transformations. We can demonstrate this proposition for $AG(4,3)$ using the
maximal cap $C$ pictured in Figure 1. A program called the Cap Builder [1]
allows a user to enter points in $AG(n,3)$ for $n=2,3,\dots,7$ that include no
lines; the program also counts the number of lines completed using points from
in the cap for each point not in the cap. In Figure 3, you see the results for
a maximal cap in $AG(4,3)$, where the letter $A$ signifies that 10 lines are
completed by that point, the anchor point. ∎

Figure 3. The maximal cap $C$ from Figure 1 showing how many lines each point
not in $C$ completes with pairs of points in $C$.

We now define demicaps. These substructures of a maximal cap have the property
that the complement of a demicap in a maximal cap is also a demicap (see
Proposition 3.7); they will also have a close connection to the partitions of
$AG(4,3)$ discussed in Section 2. An example of a demicap is pictured in
Figure 4.

######  Definition.

A _demicap_ $D$ is a cap in $AG(4,3)$ consisting of 5 pairs of points where
the line through each pair passes through a common point, $a$, called the
_anchor point_ , so that no four of these lines are co-hyperplanar.

Figure 4. A demicap with anchor point $\vec{0}$ in the upper left.

While the definition of a demicap assumes that no four pairs of points are co-
hyperplanar, in fact, a demicap cannot have eight points in the same
hyperplane even if you don’t assume they are pairs of points that make a line
with the anchor $a$. Suppose we have five pairs of points so that each pair
completes a line with $a$, and we know that eight of those points lie in the
same hyperplane. Since the eight points must include more than one of the
original pairs, and hyperplanes are line-closed, $a$ must be in that
hyperplane as well. That means those eight points must be four of the pairs of
points we started with. (Note that a hyperplane is $AG(3,3)$, and the size of
a maximal cap in that space is 9.)

As the reader might notice from the above, the next definition will make our
exposition neater.

######  Definition.

Let $a$ be a point in $AG(4,3)$. An _$a$ -line_ is a pair of points $b,c$ in
$AG(4,3)$ so that $\\{a,b,c\\}$ is a line in $AG(4,3)$.

Using this definition, a demicap consists of five $a$-lines, where no four of
them are co-hyperplanar. We will write a demicap as
$D=\\{d_{1},d_{1}^{\prime},d_{2},d_{2}^{\prime},\dots,d_{5},d_{5}^{\prime}\\}$
so that $d_{i},d_{i}^{\prime}$ is an $a$-line for $1\leq i\leq 5$.

Proposition 3.1 gives the number of lines that any point not in a maximal cap
completes with pairs of points from that cap. The next lemma shows that
demicaps have a similar structure.

######  Lemma 3.2.

Let $D$ be a cap consisting of five $a$-lines (where $a$ is necessarily not in
$D$). Then $D$ is a demicap with anchor point $a$ if and only if
$D\cup\\{b\\}$ contains at most one line, for $b\not\in D\cup\\{a\\}$.

###### Proof.

Let $a$ be a point and
$D=\\{d_{1},d_{1}^{\prime},d_{2},d_{2}^{\prime},\dots,d_{5},d_{5}^{\prime}\\}$
be a cap where $d_{i},d_{i}^{\prime}$ is an $a$-line for $1\leq i\leq 5$.

First, suppose that there is a point $b\neq a$ so that $D\cup\\{b\\}$ contains
two lines. We can relabel so that $\\{b,d_{1},d_{2}\\}$ is a line. This means
that $a,b,d_{1},d_{1}^{\prime},d_{2}$, and $d_{2}^{\prime}$ are coplanar. The
second line in $D\cup b$ can’t contain either $d_{1}^{\prime}$ or
$d_{2}^{\prime}$, or the same plane would contain five points of $D$, but five
points in a plane of $AG(4,3)$ must contain a line. Relabel so that
$\\{b,d_{3},d_{4}\\}$ is a line. This now implies that
$a,b,d_{3},d_{3}^{\prime},d_{4}$ and $d_{4}^{\prime}$ are coplanar. Thus,
$b,d_{1},d_{1}^{\prime},d_{2},d_{2}^{\prime},d_{3},d_{3}^{\prime},d_{4}$ and
$d_{4}^{\prime}$ are co-hyperplanar, so $D$ is not a demicap.

For the converse, assume that $D$ is not a demicap. Because of the assumed
structure of $D$, it must be the case that eight of the points of $D$, and
thus also $a$, are in the same hyperplane $H$. The eight points can be paired
in 28 ways; each pair has a point that completes a line with the pair. Four of
those pairs give rise to the anchor point, leaving 24 pairs. However, there
are only 27 points in $H$, and 8 of those points are in $D$. It follows that
there must be at least one point $b$ in $H$, excluding the anchor point, such
that $\\{b\\}\cup D$ contains at least two lines. ∎

The next corollary follows immediately from the previous proposition.

######  Corollary 3.3.

Let $D$ be a demicap. Then the remaining 71 points in $AG(4,3)$ consist of the
anchor point $a$, 40 points completing exactly one line with two points from
$D$, and 30 points completing no lines with points from $D$.

The next result show that all demicaps are affinely equivalent. This is our
first indication that the notion could be a useful one.

######  Theorem 3.4.

All demicaps are affinely equivalent.

###### Proof.

Let $D$ be a demicap with anchor point $\vec{0}$, so that $D$ consists of five
$\vec{0}$-lines. Let
$d_{1},d_{1}^{\prime},d_{2},d_{2}^{\prime},d_{3},d_{3}^{\prime},d_{4},d_{4}^{\prime}$
be the points from four of those $\vec{0}$-lines in $D$. We will first show
that there are exactly eight demicaps containing those points. Now
$\\{\vec{d}_{1},\vec{d}_{2},\vec{d}_{3},\vec{d}_{4}\\}$ forms a basis for
$AG(4,3)$ considered as the vector space $GF(3)^{4}$, as otherwise those four
pairs would be co-hyperplanar. Then if $d_{5},d_{5}^{\prime}$ are the last two
points in $D$, it must be true that
$\vec{d}_{5}=\sum_{i=1}^{4}c_{i}\vec{d}_{i}$ where $c_{i}=\pm 1$. (If, for
example, $c_{4}=0$, then $a,d_{1},d_{2},d_{3},d_{5}$ are all in the same
hyperplane, so there would be four pairs of co-hyperplanar points, violating
the fact that $D$ is a demicap). There are exactly 16 choices for the
coefficients $c_{i}$, giving rise to eight pairs of points that
$d_{5},d_{5}^{\prime}$ can be chosen from; those pairs are pictured in Figure
5. Let $S$ be the set consisting of these 16 points.

$a$$d_{1}$$d_{1}^{\prime}$$d_{2}$$d_{2}^{\prime}$$d_{3}$$d_{3}^{\prime}$$d_{4}$$d_{4}^{\prime}$$s$$t$$u$$v$$w$$x$$y$$z$$z^{\prime}$$y^{\prime}$$x^{\prime}$$w^{\prime}$$v^{\prime}$$u^{\prime}$$t^{\prime}$$s^{\prime}$
Figure 5. Four non-co-hyperplanar pairs of points
$d_{1},d_{1}^{\prime},d_{2},d_{2}^{\prime},d_{3},d_{3}^{\prime},d_{4},d_{4}^{\prime}$
making four lines through an anchor point $a$; any of the labeled eight pairs
of points could be added to make a demicap.

We will now show the eight demicaps found above are affinely equivalent.
Consider the linear transformations of $AG(4,3)$ that map each of the basis
elements $\\{\vec{d}_{1},\vec{d}_{2},\vec{d}_{3},\vec{d}_{4}\\}$ to either
itself or to its negative; there are 16 such transformations. If
$\vec{s}=\sum_{i=1}^{4}\vec{d}_{i}$, then each of the points in $S$ is the
image of $s$ under one of those transformations. Thus, all eight of the
possible demicaps containing
$d_{1},d_{1}^{\prime},d_{2},d_{2}^{\prime},d_{3},d_{3}^{\prime},d_{4},d_{4}^{\prime}$
are affinely equivalent.

Finally, any other demicap $D^{\prime}$ with anchor point $a$ consists of five
$a$-lines $f_{i},f_{i}^{\prime},1\leq i\leq 5$. There is a unique affine
transformation mapping $a^{\prime}$ to $\vec{0}$ and $f_{i}$ to $d_{i}$,
$1\leq i\leq 5$. That transformation then maps $\\{f_{5},f_{5}^{\prime}\\}$ to
one of the pairs of points in $S$, so $D^{\prime}$ is affinely equivalent to a
demicap which is affinely equivalent to $D$. Thus, all demicaps are affinely
equivalent. ∎

The next corollary follows from the proof of Theorem 3.4.

######  Corollary 3.5.

Let $a$ be a point in $AG(4,3)$. Given a set of four non-co-hyperplanar
$a$-lines, there are exactly eight demicaps that contain them.

The next proposition counts the number of demicaps with a given anchor. We
also count how many demicaps a given maximal cap contains and how many maximal
caps a given demicap is in. These counts will provide a link to the maximal
caps in a 1-completable pair with $C$ in Section 4.

######  Proposition 3.6.

In $AG(4,3)$:

  1. (1)

There are 101,088 distinct demicaps with a given anchor point $a$.

  2. (2)

Let $C$ be a maximal cap in $AG(4,3)$. Then $C$ contains exactly 72 demicaps.

  3. (3)

Every demicap is contained in exactly 6 maximal caps.

###### Proof.

(1) We count the number of ways to choose five $a$-lines so that no four are
co-hyperplanar. There are 40 lines through $a$, so we can choose the first two
$a$-lines to be the points from any two of those lines. Those four points
determine a plane which contains two other $a$-lines, and we cannot add any of
those $a$-lines to our demicap. This means that there are 36 $a$-lines we may
choose for the third $a$-line. The three $a$-lines chosen to this point
determine a hyperplane which contains 13 $a$-lines, so we cannot choose any of
those for our fourth $a$-line. Thus, we may choose any of the 27 remaining
$a$-lines for the fourth $a$-line in the demicap. The argument from the proof
of Theorem 3.4 shows that we could choose any of eight $a$-lines to complete
the demicap. Since the order in which we chose the $a$-lines doesn’t matter,
this gives $\frac{40\cdot 39\cdot 36\cdot 27\cdot 8}{5!}=101,088$ demicaps.

(2) Let $C$ be an arbitrary maximal cap (so $C$ consists of 10 $a$-lines). To
count the number of demicaps in $C$, we count the number of ways to choose
five $a$-lines from the 10 so that no four $a$-lines are co-hyperplanar. We
may choose any three of the 10 pairs at the start.

When we partition $AG(4,3)$ into three disjoint and parallel hyperplanes
$H_{1}$, $H_{2}$ and $H_{3}$, the intersection of those hyperplanes with $C$
partitions the cap. The only possible distribution of points in that partition
is $\\{9,9,2\\}$ or $\\{8,6,6\\}$. (This result is well-known. Davis and
Maclagan [3] call it a hyperplane triple, and Potechin [11] calls it a
division.) If we assume that the anchor point $a$ is in $H_{1}$, then the
number of points from $C$ in $H_{2}$ and $H_{3}$ must be equal, since any line
in $AG(4,3)$ is either contained in one hyperplane or it has one point from
each of three parallel hyperplanes. It follows that $H_{1}$ either contains
two or eight points of $C$.

Now, consider the partition of $AG(4,3)$ into three parallel hyperplanes
$H_{1}^{\prime}$, $H_{2}^{\prime}$, $H_{3}^{\prime}$, where $H_{1}^{\prime}$
is determined by the three pairs of points initially chosen (which forces
$H_{2}^{\prime}$ and $H_{3}^{\prime}$). There must be a fourth pair of points
from $C$ in $H_{1}^{\prime}$, by the previous paragraph, and we may not choose
that pair to be in the demicap. Thus, we may freely choose one of the six
remaining pairs not in this hyperplane.

How many choices do we have for the last pair of points from $C$? If we
consider the hyperplane containing two of the three initially chosen pairs of
points plus the fourth chosen pair, that hyperplane will contain exactly one
more pair of points (since it must contain eight points of $C$), which we
cannot add to our demicap. This excludes three of the five remaining pairs.
Either of the two remaining pairs can indeed make a demicap with the first
four chosen. Since the order we chose the pairs doesn’t matter, the total
number of demicaps in a given maximal cap is $\frac{10\cdot 9\cdot 8\cdot
6\cdot 2}{5!}=72$ demicaps.

(3) There are 8424 maximal caps with anchor point $a$ (a proof of this can be
found in [6]); from (1), there are 101,088 demicaps with the same anchor
point. From (2), each maximal cap contains 72 demicaps. An incidence count
then shows that each demicap is contained in 6 maximal caps. ∎

An alternate proof of (1) above uses the Orbit-Stabilizer Theorem. If we
assume the anchor point is $\vec{0}$, then all affine transformations fixing
$\vec{0}$ are actually linear transformations. Thus, the full group acting on
the set of demicaps with anchor point $\vec{0}$ is $GL(4,3)$, of size
24,261,120. It’s an illuminating exercise to show that the stabilizer of a
given demicap is $S_{5}\times\mathbb{Z}_{2}$, of size 240.

Our next result shows that the 72 demicaps come in 36 pairs whose union is
$C$. In the next section, this will provide a direct connection between
demicaps in $C$ and the maximal caps $C^{\prime}$ in a 1-completable pair with
$C$.

######  Proposition 3.7.

Let $C$ be a maximal cap in $AG(4,3)$, and let $D$ be a demicap with $D\subset
C$. Then $C\backslash D$ is also a demicap. Thus, every maximal cap can be
written as the disjoint union of two demicaps in 36 ways.

###### Proof.

We will show that the complement in $C$ of four co-hyperplanar $a$-lines
cannot contain a demicap. Once we have done so, then if $D$ is a demicap
contained in $C$, then its complement $C\backslash D$ cannot contain four co-
hyperplanar $a$-lines. Since the complement must consist of five $a$-lines, it
must necessarily be a demicap.

The reader can follow what we do here by considering the maximal cap in Figure
1 and the four $a$-lines in the top hyperplane, which we call $H_{1}$. These
eight points and the anchor point are nine of the 27 points in $H_{1}$.
Consider $H_{2}$ and $H_{3}$, the two hyperplanes parallel to $H_{1}$. The
complement in $C$ of those eight points consists of six $a$-lines; thus there
must be six points in $H_{2}$, and six in $H_{3}$, as hyperplanes are line-
closed and $a\in H_{1}$. If there were a demicap contained in those 12 points,
it would have to consist of five points in $H_{2}$, and five points in
$H_{3}$. Consider all pairings of these 10 points with one from $H_{2}$ and
one from $H_{3}$. There are $5\cdot 5=25$ such pairings, and each gives rise
to a point in $H_{1}$. Five of those are the anchor point, so the remaining 20
must be points other than $a$ and the eight original points, which leaves 18
points. Thus, there must be a point in $H_{1}$ that completes two lines from
the potential demicap, violating Lemma 3.2. Thus, the 12 points that are the
complement of four $a$-lines which are co-hyperplanar cannot contain a
demicap, as desired.

The last sentence of the proposition follows from Proposition 3.6 (2). ∎

We are now ready to make the connection between demicaps and pairs of maximal
caps $\\{C,C^{\prime}\\}$ that are in exactly one partition.

##  4\. Demicaps of $C$ and maximal caps that are in one partition with $C$

In $AG(4,3)$, any pair of disjoint maximal caps is in either one, two or six
partitions into four maximal caps along with their common anchor point. Given
a partition into four maximal caps plus their common anchor point, either
there are two 1-completable pairs or there are two 2-completable pairs; in
both cases, all four of the other pairs are 6-completable pairs. All this can
be found in [6]. Our goal in this section is to use one pair of demicaps whose
union is $C$ to find one of the 36 maximal caps that makes a 1-completable
pair with $C$, and then to find the unique partition of $AG(4,3)$ containing
that pair.

###  4.1. One pair of demicaps whose union is $C$ determines a maximal cap
that is in exactly one partition with $C$

Every maximal cap $C$ contains 72 demicaps. Since the complement of a demicap
in $C$ is also a demicap, there are 36 pairs of disjoint demicaps whose union
is $C$. Those pairs provide a direct link to the 36 maximal caps disjoint from
$C$ which make a 1-completable pair with $C$.

Let $C$ be a maximal cap, and $D$ a demicap contained in $C$. Let $D^{\prime}$
be the complement of $D$ in $C$. Figure 6 shows such a union for the maximal
cap pictured in Figure 1 and the demicap pictured in Figure 4.

Figure 6. The maximal cap $C$ from Figure 1 as the union of two demicaps $D$
(from Figure 4) and $D^{\prime}$.

The two demicaps $D$ and $D^{\prime}$ each have 40 points that complete one
line with a pair of points in the demicap, by Corollary 3.3. Output from the
Cap Builder [1], shown in Figure 7, indicates the points in $AG(4,3)$ that
complete one line with two points in $D$ on the left and $D^{\prime}$ in the
middle. The anchor point $a$ is the point that completes 5 lines in each
demicap.

Figure 7. The points in $AG(4,3)$ that complete one line with points from
demicaps $D$ (left) and $D^{\prime}$ (center) are indicated by 1’s. The points
that complete one line with a pair of points from both $D$ and $D^{\prime}$
are shown on the right; those points are a maximal cap $C^{\prime}$. $C$ and
$C^{\prime}$ are a 1-completable pair.

Comparing the results on the left and in the center of Figure 7, one can see
that there are exactly 20 points that complete a line with a pair of points
from $D$ and also complete a line with a pair of points from $D^{\prime}$ (the
anchor point completes five lines from each). Those 20 points are shown on the
right in Figure 7. The 20 points shown on the right in Figure 7 do indeed form
a maximal cap, as the reader can verify. Furthermore, the authors have
verified that the original maximal cap $C$ and this new maximal cap
$C^{\prime}$ are in exactly one partition.

Finally, the authors have also verified that each of the 36 pairs of disjoint
demicaps gives rise to a different maximal cap using this procedure, so the 36
pairs of disjoint demicaps whose union is $C$ correspond uniquely to the 36
maximal caps that make a 1-completable pair with $C$.

We summarize these results in a theorem.

######  Theorem 4.1.

Let $C$ be a maximal cap. There are 36 pairs of disjoint demicaps whose union
is $C$ and there are 36 maximal caps that make a 1-completable pair with $C$.
A pair of demicaps $D$ and $D^{\prime}$ where $C=D\cup D^{\prime}$ corresponds
uniquely to a maximal cap $C^{\prime}$ that is in exactly one partition with
$C$: $C^{\prime}$ consists of all the points in $AG(4,3)$ that complete one
line with a pair of points in $D$ and one line with a pair of points in
$D^{\prime}$.

Because all maximal caps are affinely equivalent and any affine transformation
sends demicaps to demicaps, verifying the theorem for one example of a maximal
cap suffices as a proof of the theorem.

###  4.2. The unique partition containing $C$ and $C^{\prime}$.

We have found a bijection between the complementary pairs of demicaps whose
union is $C$ and the maximal caps which make a 1-completable pair with $C$. Is
it possible to find the unique partition containing $C$ and $C^{\prime}$? It
turns out we already have almost everything we need to accomplish this.

Recall, we started with a demicap decomposition $C=D\cup D^{\prime}$; we then
found the 40 points completing a line with points from $D$ and the 40
completing a line with points from $D^{\prime}$, as pictured in Figure 7. Let
$S_{1}$ be the 20 points that complete a line with points of $D$ that do not
complete a line with points from $D^{\prime}$. $S_{1}$ contains lines, so it
is not a maximal cap, however, $S_{1}$ contains 12 demicaps, in six
complementary pairs. A particular one of those decompositions is shown in
Figure 9, with the two demicaps denoted $D_{1}$ and $D_{2}$. The same is true
of $S_{2}$, the 20 points that complete one line with two points from
$D^{\prime}$ but not from $D$; an example of those two decompositions is shown
in Figure 9, where the demicaps we find are denoted $D_{1}^{\prime}$ and
$D_{2}^{\prime}$.

Figure 8. Left: $S_{1}$ (20 points that complete a line with a pair of points
from $D$ but not $D^{\prime}$). Middle: $D_{1}$. Right: $D_{2}$

Figure 9. Left: $S_{2}$ (20 points that complete a line with a pair of points
from $D^{\prime}$ but not $D$). Middle: $D_{1}^{\prime}$. Right:
$D_{2}^{\prime}$.

Figure 10. Left: $M_{1}=D_{1}\cup D_{1}^{\prime}$. Right: $M_{2}=D_{2}\cup
D_{2}^{\prime}$. These are the other two maximal caps in the partition
containing $C$ and $C^{\prime}$.

Taking all possible pairings of a demicap in $S_{1}$ with a demicap in
$S_{2}$, there are only two pairings that form a maximal cap. (For all other
pairings, there are points in one demicap that complete a line with two points
from the other demicap.) Further, the two demicaps in $S_{1}$ are a
complementary pair, as are the two demicaps they are matched with in $S_{2}$.
The results obtained by pairing the demicaps from Figures 9 and 9 are shown in
Figure 10. We will call these maximal caps $M_{1}$ and $M_{2}$. The reader can
verify that $M_{1}$ and $M_{2}$ are both maximal caps.

The two maximal caps found in this way are the two other maximal caps in the
unique partition containing $C$ and $C^{\prime}$; they are themselves a
1-completable pair. We now have the unique partition that contains $C$ and
$C^{\prime}$: $\\{{\\{a\\}},C,C^{\prime},M_{1},M_{2}\\}$. That partition is
pictured in Figure 11; notice that it is a different partition than the one in
Figure 2.

The demicaps whose unions produced $M_{1}$ and $M_{2}$ are special, not
surprisingly. The pair of demicaps in $M_{1}$ is exactly the pair that
corresponds to $M_{2}$, via the correspondence given in Theorem 4.1.
Similarly, the pair of demicaps in $M_{2}$ corresponds to $M_{1}$.

* Figure 11. The partition of $AG(4,3)$ with anchor point $a$ (asterisk), $C$ (solid black circles), $C^{\prime}$ (small solid blue circles), $M_{1}$ (large red empty circles), and $M_{2}$ (small empty green circles).

We can use either $M_{1}$ or $M_{2}$ to find the partition of $C^{\prime}$
into 2 demicaps that corresponds with $C$. We will use $M_{1}=D_{1}\cup
D_{1}^{\prime}$. From Corollary 3.3, there are 40 points that complete one
line with the points in $D_{1}$; 10 of those points are in $C^{\prime}$, and
they are a demicap. The complement of those points in $C^{\prime}$ is, of
course, a demicap. $C^{\prime}$, the demicap $D_{1}$ and the two maximal caps
whose union is $C^{\prime}$ are shown in Figure 12; they provide the
decomposition of $C^{\prime}$ into demicaps that corresponds to $C$.

Figure 12. Left: $C^{\prime}$. Middle left: $D_{1}$ and the points that
complete a line with two points from $D_{1}$. Middle right: the demicap of
points in $C^{\prime}$ that complete a line with points in $D_{1}$. Right: the
demicap in $C^{\prime}$ that completes no lines with points in $D_{1}$.

We summarize these results in a proposition. As before, because all of what we
did is preserved under affine transformations, the example we used provides
the justification that this procedure will produce the same results for any
other maximal cap.

######  Proposition 4.2.

Let $C$ be a maximal cap in $AG(4,3)$, and let $C=D\cup D^{\prime}$ be a
decomposition of $C$ into two disjoint demicaps. Let $C^{\prime}$ be the
maximal cap in exactly one partition with $C$ determined by $D$ and
$D^{\prime}$ via the correspondence given in Theorem 4.1. Then:

  1. (1)

Let $S_{1}$ be the 20 points in $AG(4,3)$ that complete a line with a pair of
points from $D$ that do not complete a line with a pair of points from
$D^{\prime}$. Similarly, let $S_{2}$ be the 20 points in $AG(4,3)$ that
complete a line with a pair of points from $D^{\prime}$ that do not complete a
line with a pair of points from $D$. Both $S_{1}$ and $S_{2}$ can be
partitioned into a pair of disjoint demicaps in six ways.

  2. (2)

Exactly two of the demicaps $D_{1}$ and $D_{2}$ in $S_{1}$ can be matched with
a demicap $D_{1}^{\prime}$ and $D_{2}^{\prime}$ respectively, in $S_{2}$ so
that the union of those demicaps is a maximal cap: $M_{1}=D_{1}\cup
D_{1}^{\prime}$ and $M_{2}=D_{2}\cup D_{2}^{\prime}$. $D_{1}$ and $D_{2}$ are
a complementary pair in $S_{1}$, as are $D_{1}^{\prime}$ and $D_{2}^{\prime}$
in $S_{2}$.

  3. (3)

$\\{\\{a\\},C,C^{\prime},M_{1},M_{2}\\}$ is a partition of $AG(4,3)$ into two
1-completable pairs $\\{C,C^{\prime}\\}$ and $\\{M_{1},M_{2}\\}$.

  4. (4)

The demicap partitions given in (2) for $M_{1}$ and $M_{2}$ determines the
other maximal cap via the correspondence from Theorem 4.1.

  5. (5)

Let $D_{1}$ be one of the demicaps in $M_{1}$ as in (2). If $D^{\prime\prime}$
is the set of points in $C^{\prime}$ that complete 1 line with a pair of
points from $D_{1}$, then $D^{\prime\prime}$ is a demicap. If
$D^{\prime\prime\prime}=C^{\prime}\backslash D^{\prime\prime}$, then
$C^{\prime}=D^{\prime\prime}\cup D^{\prime\prime\prime}$ is the demicap
decomposition of $C^{\prime}$ that corresponds to $C$.

We now have the mechanism that provides a direct bijection between the demicap
decompositions of $C$ and the 36 maximal caps that make a 1-completable pair
with $C$. Even more, we can use the same pair of demicaps to identify all the
maximal caps in the unique partition containing $C$ and $C^{\prime}$, and we
can also find the demicap decomposition of each of the maximal caps in the
partition that corresponds to the other cap making a 1-completable pair in
that partition.

We can now find all 36 maximal caps that are in a unique partition with $C$,
by finding all the demicaps contained in $C$ and using the procedures
described in this section. However, in the next section, we introduce another
way to find all 36 maximal caps in a 1-completable pair with $C$, and it turns
out to be remarkably simple.

##  5\. The 36 maximal caps that are in one partition with $C$.

Our goal now is to find all 36 maximal caps that are in exactly one partition
with $C$. As seen above, we could do this by taking each of the pairs of
disjoint demicaps whose union is $C$ and following the procedure in Theorem
4.1, but there is a more illuminating way to find them.

###  5.1. Finding the 36 maximal caps in exactly one partition with $C$.

Start with a maximal cap $C$, two demicaps whose union is $C$, and the maximal
cap $C^{\prime}$ which makes a 1-completable pair with $C$, using the
procedure in Theorem 4.1. Using the procedure in Proposition 4.2, find the two
demicaps $C_{1}$ and $R_{1}$ (the choice for these names will become clear
soon) whose union is $C^{\prime}$ and which correspond to $C$ as in Theorem
4.1.

First, find the six maximal caps that $C_{1}$ is in. Notably, each of those
maximal caps is in a unique partition of $AG(4,3)$ with $C$. Find the
complement of $C_{1}$ in each of those maximal caps, one of which will be
$R_{1}$. Those six are pictured in Figure 13; the one in the upper left is
$R_{1}$. We will call these $R_{1},R_{2},\dots,R_{6}$.

Figure 13. The 6 demicaps $R_{1},R_{2},\dots,R_{6}$ whose union with $C_{1}$
is a maximal cap.

Next, find the six maximal caps that $R_{1}$ is in. Again, each of those is in
a unique partition of $AG(4,3)$ with $C$. Find the complement of $R_{1}$ in
each of those maximal caps, one of which will be $C_{1}$. Those six are
pictured in Figure 14; the one in the upper left is $C_{1}$. We will call
these $C_{1},C_{2},\dots,C_{6}$.

Figure 14. The 6 demicaps $C_{1},C_{2},\dots,C_{6}$ whose union with $R_{1}$
is a maximal cap.

The next theorem describes the significance of the demicaps $C_{i}$ and
$R_{j}$ that we have just found. The authors have verified the theorem for the
maximal cap $C$ we have been using throughout this paper. Once again, because
affine transformations preserve maximal caps, demicaps, and line incidences,
our work with that maximal cap provides the same result for all maximal caps.

######  Theorem 5.1.

Let $C$ and $C^{\prime}$ be a 1-completable pair of maximal caps, and let
$C_{1}$ and $R_{1}$ be the demicap decomposition of $C^{\prime}$ that
corresponds to $C$ via the correspondence in Theorem 4.1. $C_{1}$ is in six
maximal caps; let $R_{1},\dots,R_{6}$ be the six complements of $C_{1}$ in
those maximal caps. Similarly, let $C_{1},\dots,C_{6}$ denote the six
complements of $R_{1}$ in the six maximal caps $R_{1}$ is in. Then for any
$1\leq i,j\leq 6$, $R_{i}\cup C_{j}$ is a maximal cap. Further, the set of 36
maximal caps $\\{R_{i}\cup C_{j}\\},1\leq i,j\leq 6$ is the set of 36 maximal
caps that are in exactly one partition with $C$.

This result is surprising: those 36 maximal caps are generated by just 12
demicaps in two sets of six. This is why we used $R_{i}$ and $C_{j}$: we will
place them in rows and columns. Figure 15 shows a $2\times 3$ section of the
entire grid of 36, demonstrating the structure of these maximal caps.

Figure 15. A $2\times 3$ portion of the collection of maximal caps that are in
exactly one partition with $C$, enlarged to show detail.

The entire collection of 36 maximal caps that make a 1-completable pair with
$C$ are shown in Figure 16. One last feature is worth noting: Every point in
$AG(4,3)$ other than $a$ and the points in $C$ is either in two of the
demicaps $R_{i}$ or in two of the demicaps $C_{j}$. Thus, every point other
than $a$ and the points in $C$ is in 12 maximal caps that make a 1-completable
pair with $C$.

Figure 16. The 36 maximal caps in exactly one partition with the maximal cap
$C$, shown in Figure 1.

###  5.2. The action of the affine group and outer automorphisms of $S_{6}$.

We finish this section with an exploration of the subgroup $G$ of the affine
group that fixes $C$ as a set. Because the affine group acting on $AG(4,3)$ is
transitive on 1-completable pairs, any element of $G$ must permute the maximal
caps that make a 1-completable pair with $C$.

We start by fixing one particular maximal cap $C$. As all maximal caps are
affinely equivalent, without loss of generality we may choose the same cap $C$
we have been looking at throughout this paper (it is shown in Figure 1). As we
saw in the previous subsections, the 36 maximal caps that make a 1-completable
pair with $C$ are the unions of 12 demicaps: $\\{R_{i}\cup C_{j}\\},1\leq
i,j\leq 6$.

The affine group contains a subgroup $G$ consisting of the 2880 automorphisms
of $AG(4,3)$ that fix $C$ as a set; this subgroup is discussed in [6]. Since
$C$ is fixed as a set, the anchor point of $C$ is also fixed. Since the anchor
point for $C$ is $\vec{0}$, the subgroup of $G$ actually consists of linear
transformations. These linear transformations must permute the 36 maximal caps
which are in exactly one partition with $C$. Due to the structure of the 36
maximal caps that make a 1-completable pair with $C$, as outlined in the
previous subsection, it must also be the case that the 12 special demicaps are
also permuted by any automorphism in $G$.

Suppose we have a linear transformation $\phi\in G$. If $\phi(R_{1})=R_{i}$,
then each of the six maximal caps containing $R_{1}$ must have their images
equal to one of the six maximal caps containing $R_{i}$. On the other hand, if
$\phi(R_{1})=C_{i}$, then each of the six maximal caps containing $R_{1}$ must
have their images equal to one of the six maximal caps containing $C_{i}$.
Because each of the columns intersects each of the rows in Figure 16, if
$\phi(R_{1})=R_{i}$, then $\phi(R_{j})=R_{\sigma(j)}$ for some permutation
$\sigma\in S_{6}$. The same reasoning implies that if $\phi(R_{1})=C_{i}$,
then $\phi(R_{j})=C_{\tau(j)}$ for some permutation $\tau\in S_{6}$. That
means that the six rows and the six columns shown in Figure 16 are permuted by
$\phi$, in a particular way. A given element of $G$ either permutes the
$R_{i}$ and the $C_{j}$ separately, or it interchanges the $R_{i}$ and the
$C_{j}$.

There are two particular transformations to note: the identity transformation,
and the transformation that fixes $\vec{0}$ and reverses the two points that
make a line with $\vec{0}$. Note that the second of these two is given by the
matrix $-I$ (because the sum of the coordinates of the three points is
$\vec{0}$, and one of the points is $\vec{0}$), so that transformation must be
in the center of $G$; in addition, it fixes all lines through $\vec{0}$, so it
fixes $C$, all maximal caps that make a 1-completable pair with $C$, and all
demicaps with anchor $\vec{0}$ as sets. Thus $\\{I,-I\\}$ is a normal
subgroup, and we can take the quotient group $G/\\{I,-I\\}$ to get 1440 affine
transformations that permute the demicaps and the maximal caps that make a
1-completable pair with $C$, in different ways.

The following has been verified by using Mathematica [8]. Of the 1440 affine
transformations in the quotient group, 720 permute the set $\\{R_{i}\\},1\leq
i\leq 6$; that action is all of $S_{6}$. For ease of exposition, we will
identify the permutation on the demicaps $\\{R_{i}\\}$ by its action on the
subscripts. We have identified permutations that act as $(12)$, $(13)$, …,
$(16)$, and those permutations generate all of $S_{6}$. Similarly, those
transformations permute the set of demicaps $\\{C_{j}\\},1\leq j\leq 6$.
However, when a transformation acts on $\\{R_{i}\\}$ as (12), for example, it
permutes the set $\\{C_{j}\\}$ as, for example, $(12)(34)(56)$ (the actual
permutation will depend on how the set $\\{C_{j}\\}$ is numbered, of course,
but it will always be a product of three disjoint transpositions). Similarly,
the transformation that acts as $(12)(34)(56)$ on $\\{R_{i}\\}$ will act on
the $\\{C_{j}\\}$ as a transposition. Further, if the action of a
transformation on $\\{R_{i}\\}$ is a 6-cycle, the action of $g$ on
$\\{C_{j}\\}$ is a product of a 2-cycle and a 3-cycle. This is precisely how
outer automorphisms of $S_{6}$ work.

The other 720 permutations will interchange the sets $\\{R_{i}\\}$ and
$\\{C_{j}\\}$. This action is a bit trickier, because the permutation one gets
will depend heavily on the ordering of the $R_{i}$ and the $C_{j}$, but with a
carefully chosen numbering, the action is similar: the transformation that
maps $R_{1}$ to $C_{2}$, $R_{2}$ to $C_{1}$, and $R_{k}$ to $C_{k}$ for $3\leq
k\leq 6$, will map $C_{1}$ to $R_{2}$, $C_{2}$ to $R_{1}$, $C_{3}$ to $R_{4}$,
$C_{4}$ to $R_{3}$, $C_{5}$ to $R_{6}$, and $C_{6}$ to $R_{5}$. Again, we get
the full action of $S_{6}$ with an outer automorphism twist.

A closer look at the six demicaps $R_{1},\dots,R_{6}$ in Figure 13 shows that
each of the $R_{i}$ is the union of five of 15 $a$-lines. Further, if $i\neq
j,1\leq i,j\leq 6$, $R_{i}\cap R_{j}$ is an $a$-line. The same statements also
hold for the the six demicaps $C_{1},\dots,C_{6}$ in Figure 14, with a
different set of 15 disjoint $a$-lines. Readers familiar with the theory
behind the outer automorphisms of $S_{6}$ might notice a similarity with
synthemes and pentads, which have exactly the same structure: in the symmetric
group $S_{6}$, there are 15 synthemes, each the product of three disjoint
2-cycles. There are exactly six pentads, namely sets of 5 synthemes with no
2-cycles in common. The permutation of the pentads gives one of the standard
descriptions of the outer automorphisms of $S_{6}$. This can be found, for
example, in Rotman’s _Introduction to Group Theory_ [12].

It turns out that the action on the two block systems we’ve seen here is
actually standard. Inspired by this interesting situation, Jason Saied and
Dantong Zhu (private communication) explored transitive actions of $S_{6}$ on
sets of size 36. They found that all transitive actions of $S_{6}$ on a set of
36 elements are canonically equivalent and take the same form as above. s

##  6\. Conclusion and future work

We have defined a new substructure of maximal caps in $AG(4,3)$ that provides
a direct connection to the partitions of $AG(4,3)$ which consist of two
1-completable pairs of maximal caps. Not only does a pair of demicaps whose
union is a maximal cap $C$ provide a direct link to a particular maximal cap
$C^{\prime}$ in exactly one partition with the maximal cap that is the union
of those two demicaps, but it is also possible to use that pair of demicaps to
find the other 1-completable pair that is in the unique partition containing
those two maximal caps. In doing so, we have also identified the particular
demicap decomposition of those two maximal caps that each give rise to the
other. Further, the demicap decomposition of $C^{\prime}$ can be used to find
the full collection of 36 maximal caps that are in exactly one partition with
$C$.

There are still questions to explore, both with demicaps and with the
partitions of $AG(4,3)$ into maximal caps and their associated anchor points.
For example, here are three questions.

  * •

Given a partition that consists of two pairs of maximal caps, each of which is
in only one partition, there are four mixed pairs of disjoint maximal caps
(that is, one maximal cap from one pair and another maximal cap from another
pair). Each of those mixed pairs is in 6 different partitions. In addition,
any pair of disjoint maximal caps that are in six partitions are in only one
partition where two pairs are each 1-completable; all the other partitions
consists of two 2-completable pairs. Can demicaps be used to locate all
partitions that a 6-completable pair is in? If not, is there some other way to
find those partitions?

  * •

For a given maximal cap $C$, there are 72 maximal caps $C^{\prime}$ so that
$\\{C,C^{\prime}\\}$ are in 6 partitions. Those 72 maximal caps pair up so
that there are 36 pairs, one pair associated with each 1-completable pair that
includes $C$. Can our work here be used to distinguish those pairs?

  * •

There are two equivalence classes of partitions under affine transformations.
We have explored one of those equivalence classes. Is there a similar
substructure of maximal caps that helps to find the 2-completable pairs of
maximal caps?

Finally, it would be worth investigating whether a similar substructure of
maximal caps exists in other dimensions.

## References

  * [1] Jordan Awan.  Cap builder.  http://webbox.lafayette.edu/~mcmahone/capbuilder.html.
  * [2] Jürgen Bierbrauer.  Large caps.  J. Geom., 76(1-2):16–51, 2003.  Combinatorics, 2002 (Maratea).
  * [3] Benjamin Lent Davis and Diane Maclagan.  The card game SET.  Math. Intelligencer, 25(3):33–40, 2003.
  * [4] Y. Edel, S. Ferret, I. Landjev, and L. Storme.  The classification of the largest caps in $\rm AG(5,3)$.  J. Combin. Theory Ser. A, 99(1):95–110, 2002.
  * [5] Jordan S. Ellenberg and Dion Gijswijt.  On large subsets of $\mathbb{F}^{n}_{q}$ with no three-term arithmetic progression.  Annals of Mathematics. Second Series, 185(1):339–343, 2017.
  * [6] Michael Follett, Kyle Kalail, Elizabeth McMahon, Catherine Pelland, and Robert Won.  Partitions of $AG(4,3)$ into maximal caps.  Discrete Math., 337:1–8, 2014.
  * [7] R. Hill.  On Pellegrino’s $20$-caps in $S_{4,3}$.  In Combinatorics ’81 (Rome, 1981), volume 78 of North-Holland Math. Stud., pages 433–447. North-Holland, Amsterdam, 1983.
  * [8] Wolfram Research, Inc.  Mathematica, Version 11.3.  Champaign, IL, 2018.
  * [9] Barbu C. Kestenband.  Partitions of finite affine geometries into caps.  Linear and Multilinear Algebra, 14(3):257–270, 1983.
  * [10] Giuseppe Pellegrino.  Sul massimo ordine delle calotte in $S_{4,3}$.  Matematiche (Catania), 25:149–157 (1971), 1970.
  * [11] Aaron Potechin.  Maximal caps in ${\rm AG}(6,3)$.  Des. Codes Cryptogr., 46(3):243–259, 2008.
  * [12] Joseph J. Rotman.  An introduction to the theory of groups, volume 148 of Graduate Texts in Mathematics.  Springer-Verlag, New York, fourth edition, 1995.