\section{Counting possible distance records}\label{sec:lower}

To bound the number of landmarks from below, compare the \(n-1\) edges
next to a fixed original vertex \(i\), one on each path \(ij\).
The selection around \(i\) is common to all comparisons; the changing
part comes from the first \(k=\lfloor L/2\rfloor\) positions measured
from \(j\). The remaining positions give the same distances as a path
sharing neither endpoint with \(ij\). Choices on each edge's own path
allow only bounded repetitions of a count vector, so many different
vectors force a large total count. Fig.~\ref{fig:star} shows the
cancellation for \(L=6\), when the first three positions remain.

\begin{figure}[htbp]
\centering\input{figures/star_profiles.tex}
\caption{The three counts that matter when \(L=6\). In (a), \(e\) is the
edge next to \(i\), and \(t\) measures position from \(j\). In (b),
squares give the distances for the comparison path and circles give
the actual distances. At \(t=1,2,3\), the orange arrows move one count
from distance \(6+t\) to \(5+t\). At \(t=4,5\), the values agree.
Thus the changing part depends only on \(D_j(1),D_j(2),D_j(3)\).}
\label{fig:star}
\end{figure}

The relevant counting fact is elementary. Call the coordinate sum of
a nonnegative integer vector its \emph{cost}. For a positive integer
\(d\) and a real \(r\ge0\), the number of
vectors in \(\mathbb Z_{\ge0}^d\) with coordinate sum at most \(r\)
is \(\binom{\lfloor r\rfloor+d}{d}\), the Ehrhart count of the standard
simplex~\cite{beck}. It is at most \((r+1)^d\), because each coordinate
is at most \(\lfloor r\rfloor\). For example, in two coordinates, allowing
each vector twice gives two occurrences of cost zero, four of cost one
and six of cost two. To choose fifteen occurrences, three more of cost
three are needed. Their total cost is \(25\)
(Fig.~\ref{fig:layers}).

\begin{figure}[!htbp]
\centering\input{figures/ehrhart_layers.tex}
\caption{Fifteen occurrences of integer vectors, with at most two per
vector. In (a), the number inside a point is its number of uses.
In (b), squares count the allowed occurrences in the layer
\(r=x_1+x_2\); filled squares are used. The last column gives each
layer's contribution to the total cost \(25\).}
\label{fig:layers}
\end{figure}
\FloatBarrier



\begin{theorem}\label{thm:lower}
Let \(L\ge2\), put \(k=\lfloor L/2\rfloor\), \(Q=2^{2k+1}\), and suppose \(n>Q+1\).
Every edge multiset resolving set in \(S_L(K_n)\) contains at least
\[
 \frac n2\left(\left(\frac{n}{2Q}\right)^{1/k}-1\right)
\]
internal vertices. In particular, for each fixed \(L\ge3\),
\(\edimm(S_L(K_n))=\Omega_L(n^{1+1/k})\) whenever a resolving set exists.
\end{theorem}
\begin{proof}
Let \(B\) be the number of selected internal vertices.
For the edge \(e_{ij}\) next to \(i\), the far-endpoint columns in
\eqref{eq:columns} are
\[
 B_t(z)=
 \begin{cases}
 z^{L-1+t}-z^{L+t},&1\le t\le k,\\
 0,&k<t<L.
 \end{cases}
\]
Thus \eqref{eq:histogram} becomes
\[
 H_{e_{ij}}(z)=C_i(z)+\alpha_j(z^{L-1}-z^L)
 +\sum_{t=1}^k D_j(t)(z^{L-1+t}-z^{L+t})+E_{e_{ij}}(z),
\]
where \(C_i\) is independent of \(j\), and the support correction
\(E_{e_{ij}}\) in~\eqref{eq:local-error} depends only on selections
along \(ij\).

For odd \(L=2k+1\), assign to \(j\) the vector
\(p_j=(D_j(1),\ldots,D_j(k))\).
Once \(i,p_j\) are fixed, only \(\alpha_j\) and the \(2k\) choices on
\(ij\) can change the histogram. There are at most \(Q\) possibilities.
For even \(L=2k\), use
\(p_j=(D_j(1),\ldots,D_j(k-1),\lfloor D_j(k)/2\rfloor)\).
The parity of \(D_j(k)\), together with \(\alpha_j\) and the \(2k-1\)
choices on \(ij\), again gives at most \(Q\) possibilities.

Consequently no vector occurs more than \(Q\) times among the \(p_j\).
Indeed, for a larger proper class of equal vectors, choose \(i\)
outside that class; two of the corresponding edges would have equal
histograms. If all \(n\) vectors agree, any \(i\) gives
\(n-1>Q\) edges and the same contradiction.

The cost \(\|p_j\|_1\) of a profile is the sum of its coordinates.
At odd length, each
internal landmark contributes once to \(\sum_j\|p_j\|_1\), so the sum is
\(B\). At even length, a middle landmark is counted at both ends before
the last coordinate is divided by two. Rounding down can only decrease
the sum. Hence \(\sum_j\|p_j\|_1\le B\) in both cases.

At least half the \(n\) profiles consequently have cost at most \(2B/n\).
There are at most \((1+2B/n)^k\) possible vectors of this cost, and each
occurs at most \(Q\) times. Counting these profiles gives
\[
 \frac n2\le Q\left(1+\frac{2B}{n}\right)^k.
\]
Solving for \(B\) gives the required number of internal landmarks.
\end{proof}

\begin{corollary}\label{cor:three-lower}
For \(n\ge10\), every resolving set in \(S_3(K_n)\) contains at least
\(n^2/16-n/2\) internal vertices.
\end{corollary}
\begin{proof}
In the preceding proof \(k=1\), \(Q=8\), and
\(\sum_j p_j=B\). The minimum sum of \(n=8q+r\) nonnegative integers,
each used at most eight times, fills \(0,\ldots,q-1\) eight times
and then uses \(q\) another \(r\) times. Therefore
\[
 B\ge4q(q-1)+rq
 =\frac{n^2}{16}-\frac n2+\frac{r(8-r)}{16},
 \qquad 0\le r<8.
\]
\end{proof}

The same filling argument gives an exact finite bound in any
dimension. Lemma~\ref{lem:cost} computes the minimum total cost by
filling successive layers of integer vectors, and
Corollary~\ref{cor:exact-lower} applies this count to the endpoint
profiles above. These refinements are proved in Appendix~\ref{supp:exact}.
\FloatBarrier