7
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ If one removes the $n^2$ in the denominator - this becomes an integer sequence, maybe it is in the OEIS........ $\endgroup$ Mar 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$ Mar 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$ Apr 6, 2021 at 9:15

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.