\section{Odd lengths: Sidon labels and projected kernels}\label{sec:odd}

Let \(L=2k+1\), with \(k\ge2\). Symmetric profiles require
\(\Theta_k(n^{1+2/k})\) landmarks when \(k\ge3\)
(Corollary~\ref{cor:symmetric-odd}). To reach the exponent \(1+1/k\),
we let the counts at opposite positions vary separately. This gives
\(2k\) coordinates for each endpoint profile.
At the central edge, \(a=b=k\),
so the two endpoint columns in~\eqref{eq:columns} coincide.
Their contribution records only the sum of the endpoint profiles.
We will choose Sidon labels so that this sum identifies the pair.
Away from the center, one endpoint's change can be cancelled by a
change at the other. We must also prevent these cancellations.
For each edge position, we describe the changes that can be hidden
and bound the dimension of the space they form. This bound will allow
us to discard the conflicting pairs from a Sidon set while keeping
enough labels for all \(n\) originals.

\subsection{The linear information retained by a noncentral edge}

A noncentral edge may hide a change at one endpoint through cancellation
at the other. We bound the dimension of these changes by viewing the
histogram columns as edges between distance levels and counting the
connected components of this auxiliary graph.

Write \(\delta=2r\), where \(1\le r\le k\), and remove the common factor \(z^a\) from the columns. Let \(e_j\) be the coordinate vector for exponent \(j\) in a space with coordinates \(1,\ldots,3k+1\). Denote the resulting matrices by \(\mathcal A\) and \(\mathcal B_r\). Their columns are
\begin{align}
\mathcal A_t&=e_t-e_{L+\min(t,L-t)},&&1\le t\le2k,\notag\\
(\mathcal B_r)_t&=e_{t+2r}-e_{L+\min(t,L-t)},&&1\le t<L-r,\notag\\
(\mathcal B_r)_t&=0,&&L-r\le t\le2k.
\label{eq:incidence-columns}
\end{align}
Each nonzero column has one entry \(+1\) and one entry \(-1\), so
we can draw it as an edge joining their coordinate indices. These
indices are distance levels shifted by \(a\), because we removed
\(z^a\). The incidence-matrix rank formula converts the component count into
the dimension bound below.
Allikvere~\cite[Lemma 11]{allikvere} uses such graphs in a probabilistic
analysis of hypercube histograms.
Fix a field \(\F\), and set
\begin{equation}\label{eq:projected-kernel}
U_r=\{u\in\F^{2k}:\mathcal A u+\mathcal B_r v=0
\text{ for some }v\in\F^{2k}\}.
\end{equation}
A vector in \(U_r\) is therefore a change at the nearer endpoint whose
effect can be cancelled at the farther endpoint. To recover the nearer
endpoint, we need labels whose nonzero differences avoid every \(U_r\).

\begin{lemma}\label{lem:odd-kernel}
Over every field, \(\mathcal A\) is injective, \(\ker\mathcal B_r\) consists of vectors supported on their last \(r\) coordinates, and
\[
\dim U_r\le k-1.
\]
\end{lemma}
\begin{proof}
The \(\mathcal A\)-columns form \(k\) disjoint two-edge stars. Star \(s\) has leaves \(s,L-s\) and center \(L+s\), for \(1\le s\le k\); exponent \(L\) is isolated. Thus \(\rank\mathcal A=2k\). Each nonzero \(\mathcal B_r\)-column has smallest nonzero coordinate \(t+2r\), with coefficient one. These coordinates strictly increase with \(t\), so these columns are independent. Hence \(\rank\mathcal B_r=2k-r\) and its kernel is as stated.

To bound \(\dim U_r\), we now show that adding the
\(\mathcal B_r\)-columns joins enough of the stars.
Figure~\ref{fig:contraction} follows this step for \(k=3,r=1\):
the columns \((\mathcal B_1)_5=e_7-e_9\) and
\((\mathcal B_1)_4=e_6-e_{10}\) leave two components, and
\((\mathcal B_1)_3=e_5-e_{10}\) connects them.

Contract the \(\mathcal A\)-stars to vertices \(1,\ldots,k\), and call the isolated exponent \(L\) vertex \(0\). For every \(j>r\), the column \((\mathcal B_r)_{L-j}\) joins \(j\) to \(|j-2r|<j\). These edges form a forest with roots \(0,\ldots,r\). The component of an index is determined by its residue modulo \(2r\), up to sign: each step preserves that class and strictly decreases the index until it reaches its unique representative in \(\{0,\ldots,r\}\).

The additional column \((\mathcal B_r)_k\) joins \(k\) to \(|k+1-2r|\). Its endpoints lie in different forest components. Otherwise \(k\equiv\pm(k+1)\pmod{2r}\), which would require the even integer \(2r\) to divide either one or \(2k+1\). The contracted graph therefore has at most \(r\) components.

Contraction preserves the number of components, so the original incidence graph on \(3k+1\) vertices also has at most \(r\) components. An oriented incidence matrix on \(v\) vertices with \(c\) components has rank \(v-c\) over every field, as follows by taking a spanning forest and eliminating its leaves. Consequently,
\[
\rank[\mathcal A\ \mathcal B_r]\ge3k+1-r.
\]
Since \(\mathcal A\) is injective, it maps \(U_r\) bijectively to the intersection of the two column spaces. Thus
\[
\dim U_r=\rank\mathcal A+\rank\mathcal B_r
-\rank[\mathcal A\ \mathcal B_r]\le k-1.
\]
\end{proof}

\begin{figure}[htbp]
\centering
\input{figures/kernel_contraction.tex}
\caption{How connectivity bounds the ambiguity in
Lemma~\ref{lem:odd-kernel}, for \(L=7\), \(k=3\), \(r=1\), and \(a=2\).
In (a), the vertices are coefficient indices after removing \(z^2\).
The six blue edges are the \(\mathcal A\)-columns; three
\(\mathcal B_1\)-columns connect their boxed components.
In (b), each box becomes one vertex, retaining those connections.
The solid edges leave two components and the dashed edge joins them.
Thus the displayed columns connect all ten levels, giving rank at
least nine. Since \(\mathcal A\) and \(\mathcal B_1\) have ranks six
and five, at most two independent changes at one endpoint can be
cancelled by changes at the other.}\label{fig:contraction}
\end{figure}

\FloatBarrier
\subsection{Removing the ambiguous differences}

We remove labels whose differences lie in the spaces \(U_r\), so that
cancellation cannot hide the nearer endpoint's label. For an abelian
group, call a subset \(C\) \emph{Sidon} if every equality
\(c_1+c_2=c_3+c_4\) between elements of \(C\) gives the same unordered
pair, including repetitions. Every nonzero difference then has at most
one ordered representation, so counting the forbidden differences
bounds how many labels must be discarded.

\begin{lemma}\label{lem:pruning}
Let \(q\) be an odd prime power and \(d,s\) positive integers.
Let \(C\subseteq\F_q^d\) be Sidon, and let \(U_1,\ldots,U_s\)
be subspaces of \(\F_q^d\). There is a subset \(C'\subseteq C\) on which each quotient map modulo \(U_j\) is injective, with
\[
|C'|\ge |C|-\frac12\sum_{j=1}^s(q^{\dim U_j}-1).
\]
\end{lemma}
\begin{proof}
For each \(j\), a nonzero difference in \(U_j\) has at most one ordered representation in \(C\). The two directions of an unordered pair give distinct opposite differences because \(q\) is odd. There are therefore at most \((q^{\dim U_j}-1)/2\) unordered pairs whose difference lies in \(U_j\). Remove one endpoint of each such pair for all \(j\). The remaining set has the stated size and no two of its elements agree
in any of the quotients. Fig.~\ref{fig:pruning} illustrates the removal
for one quotient.
\end{proof}

\begin{figure}[htbp]
\centering\input{figures/sidon_pruning.tex}
\caption{Deleting ambiguous label differences. In (a), the seven points
\((x,x^2)\) in \(\mathbb F_7^2\) form a Sidon set. Projection modulo
the horizontal subspace keeps only the second coordinate; dashed lines
join the three conflicting pairs. In (b), deleting one point from each
pair leaves four different second coordinates. The deletion bound is
\((7-1)/2=3\). Elements of \(\mathbb F_7\) are drawn using their representatives
in \(\{0,\ldots,6\}\).}
\label{fig:pruning}
\end{figure}

Choose a prime \(q>k\), and fix a basis of \(\F_{q^k}\) over \(\F_q\). Since \(k\ge2\), the characteristic is odd. The classical Sidon parabola is
\begin{equation}\label{eq:parabola}
C=\{(x,x^2):x\in\F_{q^k}\}\subseteq\F_q^{2k}.
\end{equation}
Its first \(k\) coordinates specify \(x\). To recall its Sidon property, equality of two pair sums gives equal sums of the two field elements and of their squares. Since the characteristic is odd, the products also agree. The unordered pairs are the roots of the same monic quadratic; see~\cite{cilleruelo,ruiz}.

Apply Lemma~\ref{lem:pruning} to the \(k\) projected kernels of Lemma~\ref{lem:odd-kernel}, now over \(\F_q\). It gives a Sidon subset \(C'\) with injective quotient maps and
\begin{equation}\label{eq:surviving-labels}
|C'|\ge q^k-\frac{k}{2}(q^{k-1}-1)>\frac{q^k}{2}.
\end{equation}
Thus \(q^k\ge2n\) supplies \(n\) distinct labels \(c_i\in C'\). In what follows, each coordinate is represented by its integer in \(\{0,\ldots,q-1\}\).

\subsection{Balancing the labels and recovering the edges}

For each pair of positions \(s,L-s\), a zero-diagonal binary matrix
specifies the selection: a one in entry \((i,j)\) selects \(x_{ij}(s)\).
Its row \(i\) sums to \(D_i(s)\), and its column \(j\) sums to \(D_j(L-s)\).
Summing all row margins and summing all column margins count the
same selected vertices, so these two totals must agree.
The Sidon labels need not have this balance. We will adjust their last
\(k\) coordinates to obtain it, after separating the integer labels
by a fixed scale. That separation will prevent the adjustments and
the support correction from hiding a nonzero label difference.

\Needspace{12\baselineskip}
\begin{proposition}\label{prop:odd}
Let \(L=2k+1\), \(k\ge2\). Choose a prime \(q>k\) with \(q^k\ge2n\), and put
\[
K=2k+5,\qquad m=K(q-1)+1.
\]
If \(n>12\) and \(2n\ge9m+3\), then
\[
\edimm(S_{2k+1}(K_n))<k(2m+1)n.
\]
For every fixed \(k\ge2\), suitable primes give the bound \(O_k(n^{1+1/k})\) for all sufficiently large \(n\).
\end{proposition}
\begin{proof}
Take the labels just constructed, indexed by \(0\le i<n\).
We choose target values for the endpoint counts \(D_i(t)\), for \(1\le t\le2k\).
First let
\[
\mu_t=\left\lfloor\frac{K\sum_i c_{i,t}}n\right\rfloor,
\qquad R_t=K\sum_i c_{i,t}-n\mu_t\in\{0,\ldots,n-1\}.
\]
Begin with degrees \(2m+Kc_{i,t}-\mu_t\). For every \(1\le s\le k\), modify coordinate \(L-s\) in exactly \(|R_s-R_{L-s}|\) entries by \(\sgn(R_s-R_{L-s})\). Denote these corrections by \(\varepsilon_{i,t}\), setting them to zero in the first \(k\) coordinates, and write
\begin{equation}\label{eq:balanced-degrees}
D_{i,t}=2m+Kc_{i,t}-\mu_t+\varepsilon_{i,t}.
\end{equation}
Here \(D_{i,t}\) is the target value of \(D_i(t)\).
Write \(\varepsilon_i=(\varepsilon_{i,1},\ldots,\varepsilon_{i,2k})
\in\mathbb Z^{2k}\).
The number of modified entries is less than \(n\), so the choices are possible. Within a fixed coordinate all corrections belong to \(\{0,\sigma_t\}\) for a single sign \(\sigma_t\). In particular,
\begin{align}
\sum_iD_{i,s}&=\sum_iD_{i,L-s}=2mn+R_s,&&1\le s\le k,\notag\\
m&\le D_{i,t}\le3m.\label{eq:balance}
\end{align}
The bounds use \(0\le\mu_t\le K(q-1)\) and \(|\varepsilon_{i,t}|\le1\).

For each pair \(s,L-s\), realize the margins by Lemma~\ref{lem:margins}. Their total is at least \(2mn\), and their maximum is at most \(3m\). The required inequality is
\[
(3m+1)3m\le2mn,
\]
which is exactly \(2n\ge9m+3\). It also implies \(3m<n\). Select the internal vertices specified by these \(k\) matrices, and no originals. Opposite positions are distinct since \(L\) is odd. Equation~\eqref{eq:balance} gives
\begin{equation}\label{eq:odd-size}
|W|=\sum_{s=1}^k\sum_iD_{i,s}
=2kmn+\sum_{s=1}^kR_s<k(2m+1)n.
\end{equation}

There are at least \(nm\) landmarks of depth \(k\). The supports meeting either endpoint of a given edge contain at most \(12m\) such landmarks. Since \(n>12\), a depth-\(k\) landmark lies on a disjoint support, and~\eqref{eq:last-layer} identifies \(a\).

Now compare edges \(e=x_{ij}(a)x_{ij}(a+1)\) and
\(f=x_{uv}(a)x_{uv}(a+1)\) of the same depth. The global terms in~\eqref{eq:histogram} cancel, as do the constants \(2m-\mu_t\) in their endpoint profiles. For \(\mathbf x,\mathbf y\in\mathbb Z^{2k}\), define
\(\mathcal T_a(\mathbf x,\mathbf y)=
\sum_{t=1}^{2k}(x_tA_t+y_tB_t)\in\mathbb Z[z]\). Equality of histograms gives
\begin{align}
0={}&K\mathcal T_a(c_i-c_u,c_j-c_v)\notag\\
&+\mathcal T_a(\varepsilon_i-\varepsilon_u,
\varepsilon_j-\varepsilon_v)+E_e-E_f.
\label{eq:rounding}
\end{align}
Each correction difference vanishes in the first \(k\) coordinates and
has every coordinate of absolute value at most one, since its sign is fixed within each
remaining coordinate. Each endpoint map has at most \(k\) such columns,
each with coefficient norm at most one. The correction image therefore
has coefficient norm at most \(2k\). Together with~\eqref{eq:error-bound},
the second line of~\eqref{eq:rounding} has coefficient norm at most
\(2k+4<K\).
The first line has coefficients divisible by \(K\). Therefore
\begin{equation}\label{eq:exact-label-map}
\mathcal T_a(c_i-c_u,c_j-c_v)=0
\end{equation}
over the integers, and hence modulo \(q\).

If the edge is central, the two column families agree. After removing \(z^a\), each is \(\mathcal A\), which is injective. Equation~\eqref{eq:exact-label-map} gives \(c_i+c_j=c_u+c_v\) over \(\F_q\). The Sidon property identifies the unordered support, which determines its central edge.

For a noncentral edge, write \(b-a=2r\). We recover the nearer endpoint first. Equation~\eqref{eq:exact-label-map} gives \(c_i-c_u\in U_r\), so injectivity modulo \(U_r\) gives \(i=u\). The equation then becomes \(\mathcal B_r(c_j-c_v)=0\). By Lemma~\ref{lem:odd-kernel}, this kernel is supported on the last \(r\le k\) coordinates. Thus the first \(k\) coordinates of \(c_j,c_v\) agree. These specify the field element \(x\) in~\eqref{eq:parabola}, and hence the entire label, so \(j=v\). The ordered support and the already known \(a\) identify the edge. Thus every pair is distinguished.

Finally, Bertrand's postulate supplies a prime between \(X\) and \(2X\), where
\[
X=\max\{k+1,3,\lceil(2n)^{1/k}\rceil\}.
\]
For fixed \(k\), this gives \(q=O_k(n^{1/k})\), while \(m=O_k(n^{1/k})\). Since \(k\ge2\), both hypotheses on \(n\) eventually hold. Equation~\eqref{eq:odd-size} proves the asserted asymptotic bound.
\end{proof}

The scale \(K=2k+5\) used above follows from a bound of \(2k\) on
the balancing correction and four on the support error.
Lemma~\ref{lem:odd-correction} reduces the first bound to two by
examining the last \(k\) columns more closely. The combined error
is therefore at most six, allowing the fixed scale \(K=7\);
Proposition~\ref{supp:prop:odd-seven} gives the resulting finite bound.