\section{Symmetric endpoint profiles}
\label{sec:symmetric}

The lower bound suggests assigning a different short integer label to
each original vertex and realizing its coordinates as landmark counts.
We first do this with symmetric profiles. At each original vertex \(i\),
we require equal landmark counts in positions \(s\) and \(L-s\), measured
along all paths leaving that same vertex. For a fixed depth \(s\), these
counts will form the degree sequence of a simple graph. Selecting the
corresponding path positions turns these graphs into the landmark set.

The main issue is recovery. An off-center edge sees the two endpoint
labels differently, and the equations below recover them separately.
A central edge at an odd length sees only their sum. Thus arbitrary
distinct labels suffice at even lengths, while symmetric profiles at
odd lengths require distinct pair sums. This distinction will explain
why the odd-length construction of Section~\ref{sec:odd} uses asymmetric
profiles.

Put \(k=\lfloor L/2\rfloor\).
We seek a selection with endpoint counts
\[
 D_i(s)=D_i(L-s)=d_{i,s}\quad(1\le s<L/2).
\]
If \(L=2k\), the midpoint in position \(k\) has count \(D_i(k)=d_{i,k}\).
For each pair of positions \(s,L-s\) with \(1\le s<L/2\), combine
their contributions from~\eqref{eq:columns} into
\(\Phi_s=A_s+A_{L-s}\) and \(\Psi_s=B_s+B_{L-s}\). Explicitly,
\[
 \begin{aligned}
 \Phi_s&=z^{a+s}+z^{a+L-s}-2z^{L+a+s},\\
 \Psi_s&=z^{b+s}+z^{\min(b+L-s,L+a+s)}-2z^{L+a+s}.
 \end{aligned}
\]
When \(L=2k\), position \(k\) is a single midpoint, so its contribution
occurs once. Thus \(\Phi_k=A_k\) and \(\Psi_k=B_k\), namely
\[
 \Phi_k=z^{a+k}-z^{L+a+k},\qquad
 \Psi_k=z^{b+k}-z^{L+a+k}.
\]
The histogram for a selection without original vertices is
\[
 H_e(z)=\sum_{s=1}^{k}T_s z^{L+a+s}
       +\sum_{s=1}^{k}(d_{i,s}\Phi_s+d_{j,s}\Psi_s)+E_e(z).
\]

\begin{lemma}[Recovery from symmetric profiles]
\label{lem:symmetric-recovery}
For \(u=(u_1,\ldots,u_k)\) and \(v=(v_1,\ldots,v_k)\) in
\(\mathbb R^k\), consider the real linear map
\(\mathcal S_a:\mathbb R^k\times\mathbb R^k\to\mathbb R[z]\) given by
\[
 \mathcal S_a(u,v)=\sum_{s=1}^{k}(u_s\Phi_s+v_s\Psi_s).
\]
If \(\delta=b-a>0\), this map is injective.
If \(\delta=0\), which occurs only for odd \(L\), its kernel is
\(\{(u,v):u+v=0\}\).
\end{lemma}
\begin{proof}
Suppose \(\mathcal S_a(u,v)=0\).
Reading the coefficients at \(a+1,\ldots,a+k\) gives
\[
 u_s=0\quad(s\le\min(k,\delta)),\qquad
 u_s+v_{s-\delta}=0\quad(\delta<s\le k).
\]
Every other monomial of the columns has exponent above this range.
For \(\delta=0\), the two column families agree; their distinct
first exponents show that their common map is injective.
Thus the kernel is exactly \(u+v=0\).

If \(\delta\ge k\), the low coefficients give \(u=0\).
Each \(\Psi_s\) has smallest exponent \(b+s\) with positive coefficient.
These exponents strictly increase, so elimination in increasing order
gives \(v=0\).

It remains to consider \(0<\delta<k\).
For a paired coordinate \(s\), the coefficient at \(L+a+s\) gives
\[
 \begin{array}{ll}
 u_s+v_s=0,&2s>\delta,\\
 2u_s+v_s=0,&2s=\delta,\\
 2u_s+v_s-v_{\delta-s}=0,&2s<\delta.
 \end{array}
\]
Indeed, the negative terms contribute \(-2(u_s+v_s)\).
A positive second term of \(\Psi_t\) reaches this exponent precisely
when \(\min(\delta-t,t)=s\).
For \(2s<\delta\), the two indices are \(s,\delta-s\);
for \(2s=\delta\), there is the single index \(s\);
for \(2s>\delta\), there is none.
The relevant indices in the first two cases are below
\(\delta<k\), so they are always paired coordinates.
The equality case can occur only when \(L\) is odd, since then
\(\delta\) is even.
For even \(L\), the middle coordinate instead gives
\[
 u_k+v_k=0.
\]
No positive second term reaches \(L+a+k\).

The low coefficients first give \(u_1=\cdots=u_\delta=0\).
For \(\delta/2<s\le\delta\), the high equations give \(v_s=0\).
They also give \(v_s=0\) when \(2s=\delta\).
For \(s<\delta/2\), the coordinate \(v_{\delta-s}\) is already zero,
so \(v_s=0\) follows.
Finally, for \(s>\delta\), the earlier coordinate \(v_{s-\delta}=0\)
gives \(u_s=0\) through the low equation. The high equation, or the
middle equation if applicable, then gives \(v_s=0\).
Induction proves injectivity. Fig.~\ref{fig:rank} displays these dependencies for one even length.
\end{proof}


\begin{figure}[htbp]
\centering\input{figures/rank_recovery.tex}
\caption{Recovery in Lemma~\ref{lem:symmetric-recovery}, for \(L=18\), \(k=9\), \(a=7\), \(b=10\), and \(\delta=3\). In (a), the two indicated coefficients successively force \(u_s=0\) and \(v_s=0\) once \(v_{s-3}=0\). The final step \(s=9\) uses the single middle-position columns. In (b), the shaded indices are the initial zeros, and the same step reaches all remaining indices.}\label{fig:rank}
\end{figure}
\FloatBarrier

\begin{proposition}[Realizing symmetric codes]
\label{prop:symmetric-codes}
Let \(L\ge4\), \(k=\lfloor L/2\rfloor\), and let \(Q\) be a positive
integer with \(n\ge14Q\).
Suppose that \(n\) labels
\[
 c_i\in\{0,\ldots,Q-1\}^{k}
\]
are distinct when \(L\) is even. When \(L\) is odd, suppose
\(c_i+c_j=c_u+c_v\) implies \(\{i,j\}=\{u,v\}\) for all pairs with
\(i\ne j\) and \(u\ne v\).
Then \(S_L(K_n)\) has an edge multiset resolving set with symmetric
profiles and size less than
\[
 6(L-1)nQ.
\]
\end{proposition}
\begin{proof}
Choose the target degrees
\[
 d_{i,s}=6(Q+c_{i,s}).
\]
For each coordinate these degrees have even sum and lie between
\(m_0=6Q\) and \(M_0=12Q-6<n\).
Lemma~\ref{lem:graphical} applies, since
\[
 \frac{(M_0+m_0+1)^2}{4m_0}
 =\frac{(18Q-5)^2}{24Q}<13.5Q<n.
\]
Thus there is a simple graph \(G_s\) with these degrees.
For each edge of \(G_s\), select the two positions \(s,L-s\) if
\(s<L/2\). If \(L=2k\) and \(s=k\), select its single middle vertex.
The selections use distinct vertices for different coordinates and
realize the required profiles.

For a unified count, let \(w_s=2\) at a paired coordinate and \(w_k=1\)
at a middle coordinate. The number of depth-\(s\) landmarks is
\[
 T_s=\frac{w_s}{2}\sum_i d_{i,s}\ge3w_s nQ.
\]
Among these, at most
\[
 w_s(d_{i,s}+d_{j,s})<24w_sQ
\]
have supports meeting a fixed pair \(i,j\).
Since \(n\ge14Q>8\), there is a depth-\(k\) landmark on a support
disjoint from every given support.
The largest occupied histogram distance is therefore \(L+a+k\),
and it identifies \(a\).

For two edges of equal depth, subtract their histogram identities.
The global terms cancel. Every coefficient of the difference of the
linear terms is divisible by six, whereas the support-correction
difference has coefficient norm at most four.
Equality of the histograms therefore forces equality of the linear terms.

For \(\delta>0\), Lemma~\ref{lem:symmetric-recovery} recovers
the two degree vectors in order. The labels are distinct in both
parities of \(L\): in the odd case, \(c_i=c_j\) with \(i\ne j\) would
give \(c_i+c_h=c_j+c_h\) for a third index \(h\), contrary to the
pair-sum hypothesis. Distinct labels therefore determine the ordered
endpoints.
For \(\delta=0\), it recovers their sum. This pair-sum property determines
the unordered endpoints, and their support has one central edge.
This distinguishes every edge.
Finally,
\[
 |W|=\sum_s\frac{w_s}{2}\sum_i d_{i,s}
       <6nQ\sum_s w_s
       =6(L-1)nQ.
\]
\end{proof}

\begin{corollary}\label{prop:even}
Let \(L=2k\ge4\) and \(Q=\lceil n^{1/k}\rceil\).
If \(n\ge14Q\), then
\[
 \operatorname{edim}_{\rm m}(S_{2k}(K_n))<6(2k-1)nQ.
\]
For fixed \(k\ge2\), this is \(O_k(n^{1+1/k})\).
\end{corollary}
\begin{proof}
There are \(Q^k\ge n\) labels in the box.
Use any \(n\) distinct labels in
Proposition~\ref{prop:symmetric-codes}.
\end{proof}