From a question arising in Game Theory, I want to calculate the sequence $$ a_n = \max_{f_A, f_B : \mathbb{Z}_n \to \mathbb{Z}_n} \frac{\# \left\{ (x,y) | f_A(x) - f_B(y) = xy \mod n \right\}}{n^2} $$ The first terms are 1, 3/4. One could calculate subsequent terms using an exhaustive search over the functions $f$, but I feel there should be a cleverer way to do it without writing a computer program?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ If one removes the $n^2$ in the denominator - this becomes an integer sequence, maybe it is in the OEIS........ $\endgroup$– Michael Mc GettrickMar 25, 2021 at 10:49
-
$\begingroup$ I would hazard the guess that the maximum is achieved when $f_A, f_B$ are both identically zero. I don't think this results in a nice expression for the $a_n$ though (you're counting solutions to $xy=0$ over $\mathbb{Z}/n\mathbb{Z}$, and the count gets a bit messy when $n$ is not squarefree, at least when I'm doing the counting). $\endgroup$– R.P.Mar 25, 2021 at 11:37
-
$\begingroup$ I checked that RP_ - but found for $n=3$ the constant functions $f_A=f_B=0$ don't give a max (they give 5/9), instead I get a max (6/9) for example for $f_A(0)=1, f_A(1)=f_A(2)=0$, $f_B(0)=0, f_B(1)=f_B(2)=1$. $\endgroup$– Michael Mc GettrickMar 27, 2021 at 10:00
-
$\begingroup$ For prime $n$ there is an example for $cn^{4/3}$ and the upper bound for $Cn^{22/15}$ for certain positive constants $c,C$. The upper bound follows from the result of F. de Zeeuw on finite fields Szemeredi -- Trotter, the example is constructed now jointly with D. Zakharov, A. Sergunin, A. Gordeev. It is not very much explicit. If you care, I may write details. $\endgroup$– Fedor PetrovApr 6, 2021 at 9:15
Add a comment
|