🔢 mathematics

New lower bounds for constant-weight codes via seeded bit-swap tabu search

This paper presents 124 new constructions for binary constant-weight codes using seeded bit-swap tabu search, which improve existing lower bounds for $A(n,d,w)$ and consequently enhance lower bounds on the kissing numbers for dimensions 32, 33, 34, and 37.

Original authors: William Echols

Published 2026-08-17

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: William Echols

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to pack a suitcase for a trip, but with a very strange rule: every item you pack must be exactly the same size, and no two items can be too similar to each other. If they are too alike, they might get mixed up in the dark, causing chaos. In the world of digital communication, this "suitcase" is a message, the "items" are patterns of zeros and ones (bits), and the "size" is how many ones are in the pattern. This is the puzzle of constant-weight codes. Scientists use these codes to send data reliably over noisy channels, like Wi-Fi or deep-space radio, ensuring that even if a few bits get scrambled, the receiver can still figure out what was sent. The goal is simple but incredibly hard: fit as many unique, distinct items into the suitcase as possible without them bumping into each other. The bigger the suitcase (the more codes you can fit), the more information you can send at once.

Enter William Echols, who decided to tackle this packing problem with a clever twist. Instead of starting with an empty suitcase and randomly throwing items in, hoping they fit, he used a "seeded" approach. Think of it like this: if you want to build a better Lego castle, you don't just start from scratch; you take a great existing castle, pull out a few bricks, and swap them around to see if you can make it even bigger or sturdier. Echols used a computer method called tabu search, which is like a very stubborn explorer who refuses to retrace its steps (to avoid getting stuck in loops) and keeps trying new paths. By "seeding" this explorer with existing, high-quality code designs, he guided it to find 124 brand-new, larger packing arrangements that had never been discovered before. These new arrangements improve the lower limits on how many messages we can send, and they even help us understand how many spheres can touch a central sphere in high-dimensional space—a concept known as "kissing numbers."

The Packing Puzzle and the Magic Seed

In the digital world, data is just a long string of zeros and ones. Sometimes, to make things robust, we only allow strings that have a specific number of ones. For example, if we say the "weight" is 5, every string must have exactly five ones and the rest zeros. Now, imagine you have a collection of these strings. To prevent errors, every string in your collection must be different enough from every other string. If two strings are too similar, a little bit of noise could turn one into the other, and the receiver would get confused. The "distance" between them is measured by how many spots are different.

The big question in this field is: What is the maximum number of strings you can fit in your collection? This maximum number is called $A(n, d, w)$ , where $n$ is the length of the string, $d$ is the minimum distance required, and $w$ is the number of ones. For decades, mathematicians and computer scientists have been trying to find the biggest possible collections for various settings. They have found some great collections, but they often don't know if they've found the absolute biggest one. They just know they can't do better than a certain number.

The "Seeded" Strategy

Previous attempts to find these maximum numbers using computer searches often felt like wandering in a dark forest. The computers would start with random guesses, and while they sometimes found good paths, they often got stuck in local clearings that looked like the top of the mountain but weren't. They would stop there, thinking they had found the best possible code, when a much bigger one was just over the next hill.

Echols realized that the key was to stop starting from scratch. He used a technique called seeded initialization. Instead of generating a random starting point, he took a known, high-quality code (a "seed") and used it to launch the search.

He did this in two playful ways:

Direct Seeding: He took an existing code and added one extra word to it, chosen carefully to cause the least amount of "trouble" (distance deficits). This created a slightly larger, slightly messy starting point.
Neighbor Seeding: He looked at codes for slightly different problems. For instance, if he wanted a code of length 30, he might take a great code of length 29, add a zero to every word to make them length 30, and then use that as the starting point. Or, he might take a code of length 31, chop off a zero, and use that.

Once he had these "seeded" starting points, he ran his bit-swap tabu search. Imagine this search as a game of musical chairs where the chairs are the positions of the ones in the strings. The algorithm swaps bits around, trying to make the strings more distinct. The "tabu" part means the algorithm keeps a memory of moves it just made and refuses to immediately undo them, forcing it to explore new territory rather than spinning in circles.

The Results: 124 New Discoveries

By using this smart seeding strategy, Echols found 124 new constructions that beat the previous best-known records. These aren't just tiny improvements; some are massive leaps.

For example:

For a code of length 39 with specific constraints, the previous best record was 1,014 words. The new method found 1,118 words. That's a gain of 104!
For length 40, the record jumped from 1,170 to 1,230.
For length 56, the number went from 2,414 to 2,477.

These numbers represent the maximum number of unique messages we can now guarantee to send without confusion for those specific settings. The paper doesn't claim these are the absolute maximum possible (the true mathematical limit), but it proves that we can definitely do better than we thought. It pushes the "lower bound" higher, meaning we know for sure we can fit at least this many items in the suitcase.

Kissing Numbers: A Surprising Side Effect

Here is where the story gets even more interesting. The paper also touches on a concept called kissing numbers. Imagine you have a giant ball in the middle of a room. How many other balls of the same size can you pack around it so that they all touch the center ball without overlapping each other? In 3D space, the answer is 12. But in higher dimensions (like 32 or 33 dimensions), the answer is much harder to find.

The math for these kissing numbers is deeply connected to the constant-weight codes Echols found. Because he improved the codes for specific parameters (specifically $A(n, 8, 8)$ ), he automatically improved the lower bounds for the kissing numbers in dimensions 32, 33, 34, and 37.

For instance, for dimension 32 ( $\tau_{32}$ ), the previous estimate was that at least 345,408 balls could touch the center ball. With the new codes, that number jumps to 346,432. It's a small percentage increase, but in the world of high-dimensional geometry, finding even one more ball that fits is a significant victory.

The Takeaway

William Echols didn't just find a few better codes; he showed that by being smart about how you start your search—by using "seeds" from existing knowledge rather than starting blind—you can find much better solutions. The paper proves that 124 specific improvements are possible, and it gives us a new, higher floor for how much data we can reliably pack into these digital strings. It's a reminder that sometimes, the best way to move forward is to stand on the shoulders of what we already know, rather than trying to build everything from the ground up.

Technical Summary: New Lower Bounds for Constant-Weight Codes via Seeded Bit-Swap Tabu Search

Problem Statement
The paper addresses the construction of binary constant-weight codes, defined as sets of binary words of length $n$ where each word has a fixed Hamming weight $w$ and a minimum pairwise Hamming distance $d$ . The central objective is to determine $A(n, d, w)$ , the maximum size of such a code. While significant computational efforts have previously established lower bounds for various parameter sets, finding stronger bounds remains a challenging combinatorial optimization problem. Existing metaheuristic approaches, including standard tabu search, have historically yielded results weaker than known bounds or alternative algorithms.

Methodology
The author proposes a modification to Rosin's bit-swap tabu search algorithm [8] by introducing a seeded initialization strategy. Rather than initializing the search with randomly generated words, the method "warm-starts" the search using codewords from existing codes with the same or neighboring parameters.

The methodology encompasses two primary seeding techniques:

Direct Seeding: For a target $(n, d, w)$ , the algorithm utilizes an existing code $S$ of the same parameters. It constructs a library of initialization sets by appending a word $v$ to $S$ that minimizes the aggregate "distance-deficit penalty" (the sum of violations of the minimum distance constraint). The bit-swap tabu search is then executed multiple times (up to $4|E|$ , where $E$ is the set of minimal-deficit words) using random samples from this library. Crucially, the restart mechanism is omitted to preserve the provided seed.
Neighbor Seeding: This technique leverages codes from adjacent parameter sets to strengthen certificates.
- Lengthening: An existing certificate for $A(n-1, d, w)$ is extended to length $n$ .
- Shortening: A certificate for $A(n+1, d, w)$ is shortened by removing a coordinate (zero-slice) to form words of length $n$ .
- Since these intermediate codes are often smaller than the target size $s$ , the algorithm pads them with randomly chosen words of minimum penalty. While this temporarily violates the minimum-distance property, the subsequent bit-swap tabu search repairs the set into a valid code.

The implementation avoids the computational intensity of recomputing the minimal-deficit set $E$ after every insertion; instead, it computes $E$ initially and samples uniformly with replacement. The algorithm is designed to be applied successively to its own output, varying seeding methods between iterations to escape local optima.

Key Contributions and Results
The primary contribution of the work is the discovery of 124 new constructions that improve existing lower bounds for $A(n, d, w)$ . These results are verified against Brouwer's online table [2].

Constant-Weight Codes: Table 1 in the paper details improvements across a wide range of parameters. Notable gains include:
- $A(39, 8, 7)$ improved from 1014 to 1118 (+104).
- $A(40, 8, 7)$ improved from 1170 to 1230 (+60).
- $A(56, 6, 5)$ improved from 2414 to 2477 (+63).
- Significant improvements are also observed for parameters involving $d=10$ and various weights.
Kissing Numbers: As a direct corollary of the improved bounds on $A(n, 8, 8)$ $A (n, 8, 8)$ for $n \in \{32, 33, 34, 37\}$ $n \in {32, 33, 34, 37}$ , the paper derives improved lower bounds for the kissing numbers $\tau_n$ $τ_{n}$ . Specifically:
- $\tau_{32}$ is improved from 345,408 to 346,432 (+1,024).
- $\tau_{33}$ is improved from 360,640 to 362,048 (+1,408).
- $\tau_{34}$ is improved from 380,868 to 381,124 (+256).
- $\tau_{37}$ is improved from 494,312 to 496,232 (+1,920).

Significance and Claims
The paper claims that the proposed seeded initialization approach effectively overcomes the limitations of previous tabu search implementations, which had previously resulted in weaker bounds. By utilizing information from equivalent and neighboring parameter sets, the method successfully navigates the search space to find stronger lower bounds where random initialization failed. The work serves as a practical demonstration that "warm-starting" metaheuristics with high-quality seeds derived from related coding problems can yield immediate, verifiable improvements in combinatorial coding theory. The author provides the generated codes publicly to facilitate further verification and research.