# Sidon pair encoding

- ID: 1945
- Canonical URL: https://synthcore.org/idea/1945/sidon-pair-encoding
- API JSON: https://synthcore.org/api/idea/1945.json
- API Markdown: https://synthcore.org/api/idea/1945.md
- Verification status: unverified
- Source: [arXiv:2608.07416](https://arxiv.org/abs/2608.07416)
- Category: architecture
- Solves: accuracy, memory, generalization
- ML areas: embedding, attention, graph-nn, quantization
- Math tags: combinatorics, number-theory, linear-algebra
- Ratings: usefulness 5/10; difficulty 4/10; novelty 7/10

## Idea description

Assign each of K entity or token types an integer code from a B_{2,\Delta}-set A, so every unordered pair {i,j} produces a unique and margin-separated scalar code a_i+a_j. Use this code as a compact symmetric pair feature for graph edges, attention biases, or pairwise relation MLPs, avoiding collisions that occur when ordinary low-dimensional additive encodings are quantized or hashed.

## Mathematical statement

A set A of integers is \Delta-separated when |a-a'|\geq\Delta for every distinct a,a'\in A. It is a B_2-set, also called a Sidon set, when every element of 2A={a+b:a,b\in A} has a unique representation as an unordered sum; equivalently, a+b=c+d implies {a,b}={c,d}. A B_{2,\Delta}-set satisfies the stronger condition |(a+b)-(c+d)|\geq\Delta whenever {a,b}
eq\{c,d\}. Therefore the map from an unordered pair {i,j} to a_i+a_j is injective and has minimum scalar margin \Delta. Lemma 1 in the paper states that if hA is \Delta-separated, then (h-1)A is \Delta-separated; for h=2, separation of pair sums implies separation of A itself. The paper also gives the dilation identity (\Delta\ast A)(x)=A(x/\Delta), where \Delta\ast A=\{\Delta a:a\in A\}; multiplying all codes by \Delta increases the pair-sum margin by the same factor. In the neural adaptation, a_i is the fixed integer code for entity i, s_{ij}=a_i+a_j is the pair feature, and perturbations smaller than \Delta/2 cannot cause nearest-code confusion.

## Key formulas

- $$A\text{ is }\Delta\text{-separated}\iff |a-a'|\geq\Delta\quad\forall a\neq a',\ a,a'\in A.$$
- $$B_2:\quad a+b=c+d\ \Longrightarrow\ \{a,b\}=\{c,d\};\qquad B_{2,\Delta}:\quad |(a+b)-(c+d)|\geq\Delta\quad\text{whenever }\{a,b\}\neq\{c,d\}.$$
- $$(\Delta\ast A)(x)=A\left(\frac{x}{\Delta}\right),\qquad \Delta\ast A=\{\Delta a:a\in A\}.$$
- $$s_{ij}=a_i+a_j,\qquad \phi_{ij}=\operatorname{MLP}\left(\frac{s_{ij}}{S}\right),\qquad S=\max_{u,v}|a_u+a_v|.$$

## Implementation notes

Integrate this at the pair-feature stage of a graph neural network or transformer with symmetric entity interactions. First choose K entity types and construct an integer set A inside [0,N] using a greedy B_{2,\Delta} procedure. Initialize A and the occupied sum list as empty; scan candidate integers x; reject x if |x-a|<\Delta for any existing code a, if any new sum x+a or 2x lies within distance \Delta of an occupied sum, or if two newly generated sums are closer than \Delta; otherwise accept x and add its new sums. Compact pseudocode is: `A=[]; sums=[]; for x in candidates: new=[x+a for a in A]+[2*x]; if min_distance(x,A)>=Delta and min_distance(new,sums)>=Delta and min_pairwise_distance(new)>=Delta: A.append(x); sums.extend(new); if len(A)==K: break`. Store the resulting codes as a non-trainable vector a. For each unordered pair, compute s=a[i]+a[j], normalize by S=max_{u,v}|a[u]+a[v]|, and concatenate it to the usual edge or attention feature before an MLP. In attention, use `logit_ij = q_i dot k_j / sqrt(d) + w^T MLP(s_ij/S)`. Optionally quantize s to int8 or add bounded noise and decode to the nearest valid sum; the B_{2,Delta} guarantee gives tolerance below Delta/2. The mathematical quantities are the injective pair-sum map and its separation margin; the code range N, MLP weights, and normalization are empirical design choices. Start with a 20-node synthetic graph task where labels depend on arbitrary unordered node-type pairs. Compare Sidon codes, random integer codes, and learned scalar codes at equal pair-feature width, with and without int8 quantization. Measure collision rate, pair-label accuracy, robustness under additive noise, code range, and memory. Success is zero collisions by construction and higher accuracy or lower pair-feature memory at equal model size.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.