\documentstyle{letter}

\begin{document}

{\Large\bf On proving existence of some circle packings in a square using
computer algebra systems}\\

{P\'{e}ter G\'{a}bor Szab\'{o}}\\
{\small
Department of Applied Informatics, University of Szeged\\
H-6701 Szeged P.O. Box 652, Hungary\\
Phone: +36 62 544-222/3408 ext.\\
Fax: +36 62 546-397\\
E-mail: {\tt pszabo@inf.u-szeged.hu}}\\

The problem is the following: Locate $n$ equal and non-overlapping circles in a
square, such that the radius of the circles be maximal.

Up to $n=5$ circles the problem is trivial and there are solutions for
$n$=6,8,9,14,16,25 and 36 using only mathematical tools. Since 1990 real
improvements were made in this field based on computer aided methods.
Using deterministic optimization techniques, the optimal packings are known up
to $n=30$ [3]. For higher $n$ values (with the exception of $n=36$, when the
solution is known) stochastic methods (e.g. Threshold Accepting, billiard
simulation [2], etc.) can be used to find good approximate packings.

It is important to realize that an approximate packing found by the computer
is not always sure in the mathematical sense. The structure suggested by the
numerical result is only a kind of conjecture, because the rounding errors can
produce serious mistakes. We have to prove that the structure of a given
packing really exists, that it is feasible.

A possible approach is based on algebraic, symbolic computations [1]. Find the
corresponding suitable quadratic system of equations to the packing and try to
solve it. In this case the computer algebra systems can help the
investigation. The talk will show recent results in this field. \\

\noindent
{\bf References}

{\small 
\noindent [1] P.G. Szab\'{o}, Optimal substructures in optimal and approximate
circle packings, {\it Beitrage zur Algebra und Geometrie} (Accepted for
publication).

\noindent [2] P.G. Szab\'{o} and E. Specht, Packing up to 200 equal circles in a
square, (Submitted for publication).

\noindent [3] P.G. Szab\'{o}, M.Cs. Mark\'{o}t, and T. Csendes, Global optimization in
geometry --- Circle packing into the square (Submitted for publication).}

\end{document}

