4
$\begingroup$

Does the following limit exist? $$ \lim_{n \to \infty}\, n^{-3/2} \min_{a_{ij}=\pm 1}\max_{x_{j}=\pm 1}\left|\sum_{1\leq i <j \leq n} a_{ij}x_{i}x_{j} \right| $$ There is no any significant motivation behind this question, it is just a pure curiosity.

I am not really interested in numerical computations, and proofs of upper or lower bounds unless they provide significant evidence that the limit does not exist. In case the limit exists I am curious what is the proof?

Improve this question
$\endgroup$
9
  • $\begingroup$ As the absolute value does not really change anything (by symmetry), the answer to your question equals to $\frac 12 \lim_{n \to \infty}\, min_A max_x n^{-3/2} x^TAx$ where $A$ is an $n\times n$ size $\pm 1$ matrix and $x\in \{\pm 1\}^n$. Because of this, I think that you should use very different tags for your question. $\endgroup$
    – domotorp
    Commented Jan 16, 2022 at 9:07
  • $\begingroup$ @domotorp why can you remove the absolute value? $\endgroup$
    – Paata Ivanishvili
    Commented Jan 16, 2022 at 12:44
  • $\begingroup$ Sorry, my bad, I take that part back. Still, I feel that this has more to do with eigenvalues than with discrepancy. $\endgroup$
    – domotorp
    Commented Jan 16, 2022 at 14:19
  • 1
    $\begingroup$ @ShannonStarr I agree with upper bounds. Lower bounds are more tricky. I can show that liminf is at least $C>0$. If my calculus is correct then $C=2^{-5/2}$ works. Perhaps I can do better than $2^{-5/2}$, but these arguments that I know do not prove/disprove existence of the limit. $\endgroup$
    – Paata Ivanishvili
    Commented Jan 17, 2022 at 2:48
  • 1
    $\begingroup$ @ShannonStarr, here is one way to get a lower bound, see Theorem of Defant--Mastylo--Perez applied to 2-homogeneous polynomial f, extremal010101.wordpress.com/2019/12/06/… Thanks for the references and the names. $\endgroup$
    – Paata Ivanishvili
    Commented Jan 18, 2022 at 1:19

0

Reset to default

You must log in to answer this question.