22
$\begingroup$

I am curious if the following seemingly simple question has an easy answer?

Consider an ant population of $N$ ants that lives in $\mathbb R^2$. Each ant can be labeled by some coordinate $x\in \mathbb R^2.$

Ants like to be close to their peers but also not too close. The optimal distance between the center of two ants is $5^{2/3}$. So given two ants $x_i,x_j \in \mathbb R^2$. Their happiness $H$ is $$H(x_i,x_j):=\operatorname{max}\{-\vert \vert x_i-x_j \vert^{3/2} -5 \vert,-10\}.$$

Distances $\vert x_i-x_j\vert \le 1$ are not allowed since ants do not like to get too close.

The purpose of the maximum, in the definition of $H$ above, reflects that there is no attraction between two ants anymore at a certain distance.

Now consider the total happiness $H_N:=\sum_{i<j} H(x_i,x_j).$ The question is the following:

Let $x=(x_1,..,x_N)$ be any global minimizer of the happiness $H_N.$ Can we find a radius $r$ such that all ants of a global maximiser of the happiness are within a distance $r\sqrt{N}$ from one another?

The scaling $r\sqrt{N}$ is due to the fact that order $N$ lattice particles would fit into a ball of radius $r\sqrt{N}.$

The question sounds almost like a school problem, and may admit a very simple solution, if one finds the right way of arguing here, but it seems just hard to exclude the huge amount of bizarre configurations.

$\endgroup$
  • 3
    $\begingroup$ Why the exponent $3/2$ in the definition of $H(x_i,x_j)$? With it, the minimum of $H$ is when $|x_i-x_j|=5^{2/3}$, not 5. $\endgroup$ – Joël Jan 13 at 4:47
  • 2
    $\begingroup$ I take it $x_i$ aren't really ants, rather, they are the centers of ants? $\endgroup$ – Gerry Myerson Jan 13 at 5:03
  • 4
    $\begingroup$ @LSpice we will allow our ants to experience a certain level of intimacy ;) $\endgroup$ – Pritam Bemis Jan 13 at 6:48
  • 5
    $\begingroup$ @Joël is it really concave? $|x^{3/2}-5|$ is sometimes $x^{3/2}-5$, sometimes $5-x^{3/2}$ --- opposite convexities. $\endgroup$ – Fedor Petrov Jan 13 at 19:46
  • 3
    $\begingroup$ @PritamBemis: It would be better rephrasing this using potentials $V=-H$ and talk about global minimizers of the total potential rather than maximizing happiness. This would allow you to connect your question to the vast existing literature on this kind of problems, i.e., proving cristalization. You should, in particular, look up the work of Sylvia Serfaty and collaborators. $\endgroup$ – Abdelmalek Abdesselam Jan 14 at 15:52
3
+500
$\begingroup$

I am going to describe a partial solution / proposal to obtain a solution, which I think is interesting enough to post even though it doesn't fully answer the question.


First, I wish to redefine $H(x_i,x_j)$ as $\max \{ 10 - | | x_i - x_j|^{3/2}-5|,0\}$, i.e. add $10$ to make it nonnegative.

Having done this, we obtain $\max H_{N_1+N_2} \geq \max H_{N_1} + \max H_{N_2}$, so $\lim_{N \to \infty} \frac{ \max H_N}{ N} $ exists and is either finite or $+\infty$. There is some limit to the happiness $\sum_j H(x_i,x_j)$ of an individual ant based on the number of discs of radius $1/2$ we can pack into a disc of radius $15^{2/3}$, so it is not $+\infty$ and thus is finite. Call this $\lambda$.


My approoach rests on the following conjecture:

There exists a constant $c>0$ such that, for any configuration of $N$ ants, such that the graph with vertices ants and edges pairs of ants separated by a distance of at most $15^{2/3}$ is connected, the total happiness is at most $\lambda N - c R$ where $R$ is the minimal radius of a disc enclosing all the ants.

The motivation for this conjecture is that, whatever configuration gives the maximum $\lambda$ happiness per ant, the boundary of the ant colony will form a flaw in that configuration, leading to a loss from the maximal $\lambda N$ happiness proportional to the size of the boundary. Under this mild connectedness hypothesis, $R$ is bounded by the size of the boundary, explaining the lost happiness proportional with $R$.

Combined with the statement that, for all $N$, there exists a configuration of happiness at least $\lambda N - O (\sqrt{N})$, this implies an upper bound as you desire.

However, I am not sure how to prove the conjecture without a more precise understanding of the optimal configuration - it is possible to imagine, say, packing ants in some highly efficient way which can't be continued past a certain curve, leading to very happy configurations with large boundary.


I will now prove the existence statement.

Take a configuration of a very large number of ants that attains an average happiness of $\lambda-\epsilon$. Let $r$ be minimal such that a ball of radius $r$ can pack at most $n$ ants. Consider a random disc of radius $r$ in this large configuration. The expected number of ants in this disc is $ d \pi r^2$ where $d$ is the density. The expected total happiness of the ants in the disc is $(\lambda-\epsilon) d \pi r^2$. The expected number of ants in the disc within a distance $15^{2/3}$ of the boundary is $ O ( d \pi r)$ and so the expected loss to the happiness of the ants in the disc from removing all the ants outside the disc is $O( d \pi r)$. So the expected total happiness of the ants in the disc, once the outside ants are removed, is $$ \geq (\lambda - \epsilon ) d \pi r^2 - O( d \pi r).$$

So there must exist some configuration of $\leq n$ ants whose average happiness is at least

$$ \frac{ (\lambda - \epsilon ) d \pi r^2 - O( d\pi r)}{ d \pi r^2} = \lambda - \epsilon - O \left( \frac{1}{r} \right)$$

We have $r \approx \sqrt{n}$ so this is $$\lambda - \epsilon - O \left(\frac{1}{\sqrt{n} }\right).$$ Taking $\epsilon$ to $0$, we see that there is a configuration of $m \leq n$ ants with happiness $\geq m \lambda - O\left( \frac{m}{\sqrt{n}}\right)$.

I claim that there is a configuration of exactly $N$ ants with happiness $\lambda N - O ( \sqrt{N})$. To see this, take $n_1= N$ and find a configuration of $m_1$ ants with average happiness $\geq \lambda - O( \frac{1}{\sqrt{n_1}})$, then repeat it $ \lfloor \frac{n_1}{m_1} \rfloor$ times, leaving room for $n_2 = n_1 - m_1 \lfloor \frac{n_1}{m_1} \rfloor$ ant. Then apply the previous existence result again to find a configuration of at most $n_2$ ants with average happiness $\geq \lambda - O ( \frac{1}{ \sqrt{n_2} })$ , and iterate. The total happiness is $$\geq \lambda N - \sum_i \left\lfloor \frac{n_i}{m_i} \right\rfloor O \left( \frac{m_i}{ \sqrt{n_i}}\right) \geq \lambda N - \sum_i O \left(\sqrt{n_i} \right) = \lambda N - O (\sqrt{N})$$ since $n_{i+1} < n_i/2$ so $n_i < N/ 2^{i-1}$.

$\endgroup$
  • $\begingroup$ How do we take $\varepsilon\to 0$ without blowing up $n$? $\lambda$, as defined, is just the limit, not something to be (almost) attained for any fixed $n$. Am I missing anything? $\endgroup$ – fedja Jan 20 at 3:21
  • $\begingroup$ @fedja The number blowing up is the "very large number of ants" which I didn't name because it doesn't actually appear anywhere in the calculation. $n$ is fixed, and exists to determine the radius $r$. $\endgroup$ – Will Sawin Jan 20 at 3:23
  • $\begingroup$ Thanks. Now it is clear :) $\endgroup$ – fedja Jan 20 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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