5
$\begingroup$

Suppose I had T points in the interval $[0,1]$. Call them $e_1, \dots, e_T$.

Question 1: What is a good nontrivial bound on the geometric mean of $$\{|e_i - e_j| : 1 \leq i < j \leq T \}, $$ as a function of $T$, independent of our choice of $e_i$?

Question 2: Suppose we can choose $i$ that minimizes the geometric mean of $$E_i = \{ |e_i-e_j| : 1 \leq j \leq T, j \neq i \}.$$What is a good nontrivial upper bound on the geometric mean of $E_i$ as a function of $T$?

Some context:

Suppose I were given an arithmetic circuit that computes $$f(z) = \sum_{i=1}^t c_tz^{e_t},$$ with bounds $D$ on the degree and $T$ on the number of terms, and we would like to test whether $f$ is zero. One way to test this for $f$ over an arbitrary field is to compute images $f \bmod (z^p-1)$ for a set comprised of the smallest primes $p$ whose product exceeds $$\prod_{j \neq 1} (e_1 - e_j),$$ though one could replace $e_1$ with any of the $e_i$'s. A naive upper bound on this product is $D^T$. An answer to either of the questions above could improve this bound.

$\endgroup$
1
  • $\begingroup$ Could you give more explanation of the context, and what you’ve tried? Without any background, this looks a bit like it’s a homework problem or similar, in which case it’s off-topic here (Mathoverflow is aimed at research-level mathematics) and would be a better fit at math.stackexchange.com. $\endgroup$ Oct 18, 2013 at 22:06

1 Answer 1

5
$\begingroup$

The extremal $e_i$ for Question 1 are probably well-known: they are $0$, $1$, and $(1+r)/2$ where $r$ ranges over the roots of the Gegenbauer polynomial $C_{T-2}^{(3/2)}$. The product of the $|e_i-e_j|$ is then a power of $2$ times the square root of $\mathop{\rm disc}\bigl((x^2-1)C_{T-2}^{(3/2)}(x) / c_{T-2}\bigr)$, where $c_n$ the leading coefficient $(2n+1)!/2^n n!^2$ of $C_n^{(3/2)}$. This discriminant can in turn be computed from the values of $C_{T-2}^{(3/2)}$ at $\pm 1$ and the discriminant of $C_{T-2}^{(3/2)} / c_{T-2}$, which is known but somewhat complicated $-$ experimentally it seems to be $$ \prod_{m=1}^{T-2} \frac{(m+2)^{m-2}m^m}{(2m+1)^{2m-3}}. $$ To prove that these are the optimal $e_i$: let $P(x) = \prod_{i=1}^T (x-e_i)$ and suppose $\{e_i\}$ maximizes $\prod_{i<j} |e_i-e_j|$. Then clearly two of them are at $0$ and $1$. I claim that each of the others is a root of $P''$. Indeed $e_i$ is a local maximum of $P(x)/(x-e_i)$, so a root of $\frac{d}{dx}(P(x)/(x-e_i))$, so a triple root of $(x-e_i)P'(x)-P(x)$; but then it's a root of $\frac{d^2}{dx^2}\bigl((x-e_i)P'(x)-P(x)\bigr)$, whose value at $x=e_i$ is $2P''(e)$. It follows that $P$ is a multiple of $(x^2-x)P''$, and by comparing leading coefficients we see that the multiple is $T^2-T$. The resulting differential equation characterizes $(T^2-T)C_{T-2}^{(3/2)}(2x-1)$ among polynomials up to scaling, so we are done.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.