4
$\begingroup$

(This question is inspired by Erich's Packing Center.
I'm just asking about circles in squares to keep things simple, since I suspect
any answer would apply just-as-well to the rest of the problems on that page.)

Define $\: \hspace{.04 in}f : \{\hspace{-0.04 in}1,\hspace{-0.03 in}2\hspace{.02 in},\hspace{-0.04 in}3,\hspace{-0.04 in}4,\hspace{-0.04 in}5,...\hspace{-0.04 in}\} \to [0,\hspace{-0.04 in}\scriptsize+\normalsize \infty \hspace{-0.02 in}) \;$ by letting $\hspace{.04 in}f(n)$ be the side length of the smallest square that
$n$ unit circles can be packed inside. $\;\;\;$ (The existence of a minimum follows from compactness.)

In terms of $n$, what upper bounds are known on the size of algebraic representations of $\hspace{.04 in}f(n)$?



I imagine that "algebraic representations" would mean with

$\;$ the constant $-1$
$\;\;\;\;$ and
$\;$ the binary operations plus and times
$\;\;\;\;$ and
$\;$ extracting a root from a single-variable polynomial given
$\;$ its coefficient-vector and an interval that brackets the root

.


The Only Upper Bound I Know:

For each $n$, $\hspace{.04 in}f(n)$ is the smallest value of the unique free variable in a $\Theta(n)$-variable
existential formula over the reals with $\Theta(n)$ other symbols that satisfies the formula.
Since the quantifiers can be eliminated from such a formula in $n^{O(n)}$ time and the operations plus and times are continuous, $\hspace{.04 in}f(n)$ is a solution to a univariate equation of length $n^{O(n)}$ in the first-order theory
of the reals that does not hold identically. $\:$ With some work (to see that size doesn't blow up), one can
see that such equations are equivalent to standard-form single-variable integer-coefficient polynomial equations of length $n^{O(n)}$ that do not hold identically. $\:$ By Theorem 1.2 (or any root separation bound
that's not much worse), $\hspace{.04 in}f(n)$ can be bracketed by an interval whose endpoints are rationals with $n^{O(n)}\hspace{-0.02 in}$-bit denominators. $\;\;\;$ Since $\: 0\leq \hspace{.02 in}f(n) \leq poly(n) \:$ holds for all $n$, those rationals can be chosen so that additionally their numerators are $n^{O(n)}$ bits long. $\;\;\;$ Thus, $\hspace{.04 in}f(n)$ can be given by a rational interval that brackets a root of an integer-coefficient polynomial such that the total size of that representation is $n^{O(n)}$.

Is anything better known?

${}$

Improve this question
$\endgroup$
7
  • $\begingroup$ You're citing slightly outdated complexity results for quantifier elimination; they were improved by Basu-Pollack-Roy, cf e.g. perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted1.html I don't know whether this improves your bound (perhaps it does, to something like $p(n)2^{O(n)}$, for $p$ a polynomial). $\endgroup$
    – Dima Pasechnik
    Mar 31, 2015 at 19:54
  • $\begingroup$ I'm looking at Exercise 11.9 from the "For downloading the .pdf file of the book" link on the page you linked to, and as far as I can see, that will only improve on the result I cited when $\ell$ is $(\Omega(1))^k$ (using the notation of Algorithm 11.16). $\;$ $\endgroup$
    – user5810
    Apr 1, 2015 at 0:23
  • $\begingroup$ Could you explain how the formula you are eliminating from looks like? E.g. for optimisation they have Sect. 14.2 which might give a better bound... $\endgroup$
    – Dima Pasechnik
    Apr 1, 2015 at 9:00
  • $\begingroup$ Essentially, "there are $\:2\cdot n\:$ reals such that the $n$ points described by those reals are each at most $\:r+1\:$ from the origin and at least $2$ from each other". $\;\;\;$ Thus, $s$ would be quadratic in $n$. $\:$ Do you know where they address the sizes of the coefficients produced by their global optimization algorithm? $\;\;\;\;\;\;\;$ $\endgroup$
    – user5810
    Apr 1, 2015 at 9:32
  • $\begingroup$ If there is a bound on the bit-lengths of the coefficients that is better than $n^{O(n)}$, then that would yield a better bound for my problem (in particular, enough for the bounty), since it would provide an explicit constant for the main factor of the runtime. $\:$ (i.e., $n^{\hspace{.02 in}O(n)}$ becomes $\: n^{\hspace{.02 in}c\cdot n} \cdot \text{something_asymptotically_smaller_than_that} \;$.) $\;\;\;\;\;\;\;$ $\endgroup$
    – user5810
    Apr 1, 2015 at 9:33

0

Reset to default

Your Answer

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