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}$.

centersof ants? $\endgroup$14more comments