The Hunt for Legendre Pairs of Length 117
Your computer can help settle a question mathematicians have been asking since 1893.A crowd-sourced search on DCP for two ±1 sequences of length 117 whose autocorrelations sum to −2 at every shift. None is known. Explore a region, sponsor the search, run a worker, and share the prize pool if your region holds half of a pair.
The space
Every patch is a fixed block of slices taken on both sides, A and B, laid along a Hilbert curve so neighbouring patches stay neighbours. Black is unexplored, white is fully explored, red shading is the density of A candidates found there, blue the density of B candidates. Scroll to zoom, hover for details, and click to select one or more patches to search; you can add your organization's logo, and adjacent searched squares of yours merge into one larger logo.
Explore a patch
Zoom in on the search space and select as many patches as you would like to explore for A and B legendre pair candidates. Find a pair half to win the pool DCC prize.
Launch a worker
Open dcp.live/?computeGroups=legendre117,jointhehunt on any computer or device and click Start to compute pieces of the search space. If you like the browser worker, consider running a native one: see distributive.network for DCP Worker options.
WorkExplorers
Most A candidates found
Nobody yet.
Most B candidates found
Nobody yet.
The prize pool
A share of every credit spent on this search goes into a pool for the people who find a pair. A pair has two halves, found in two patches, usually by two explorers: the award for that pair is split between them.
| pair found | share of the pool | status |
|---|
5% of the credits paid for completed slices; the schedule halves with each pair found. Slices from jobs that did not record a price count at the default rate. Payout mechanics are not built yet.
Pairs
No verified pair yet. When two records on the A and B sides share a key, the sequences are rebuilt and checked exactly; only a proven pair appears here.
How the search works
Length 117 = 9 × 13. Every candidate is a 9-uncompression of a known length-13 seed, which leaves 1.55 × 10²⁵ sequences per side. Three pieces of structure make the search about ten thousand times cheaper than the 2022 brute force:
The spectrum has layers
Fold 117 entries into 39 by adding positions 39 apart. At every frequency divisible by 3, the folded sequence has the same spectrum, so 13 of the 51 constraints are decided on 1.2 × 10¹³ short sequences instead of 10²⁵ long ones. About 1 in 100,000 survive.
Most entries are invisible
At the other frequencies, columns with three equal entries cancel exactly (1 + ζ + ζ² = 0). Only the ~30 columns with an odd entry matter, each a choice among 3 positions. Those 3³⁰ choices are walked in Gray-code order, one complex add per frequency per step, on the GPU.
Symmetry
Shifts by 13, five multipliers and reversal give every candidate 107 twins that are pairs together or not at all. One representative per orbit is searched, 105 times fewer sequences, verified against the known case of length 45.
Workers send compact records (an exact key of the sequence's autocorrelations, plus where it was found) to a relay. A nightly join looks for a key present on both sides and proves any match on the sequences themselves. Code and write-up.
Why it matters
A Legendre pair of length ℓ builds a Hadamard matrix of order 2ℓ + 2: a square of +1 and −1 entries whose rows are all mutually orthogonal. Hadamard matrices are the backbone of a surprising amount of engineering. Walsh–Hadamard codes separate the channels in CDMA mobile networks; the Reed–Muller codes built from them carried Mariner 9's pictures of Mars; Hadamard masks multiplex light in spectrometers and single-pixel cameras; Plackett–Burman screening designs, which are Hadamard matrices in disguise, decide which factors matter in industrial experiments; and compressive sensing and some quantum-information constructions lean on them too. Circulant-structured Hadamard matrices, the kind a Legendre pair produces, are the practical ones: they need almost no storage and their transforms run through the FFT.
To be clear about the prize itself: Hadamard matrices of order 236 already exist (every order below 668 is known), so a pair of length 117 would give a new, structured matrix of that order, not the first one. The mathematical stake is larger than one matrix. Legendre pairs are conjectured to exist for every odd length, which would imply the Hadamard conjecture, open since 1893. Length 117 is among the smallest lengths with no known pair and the first open case for lengths divisible by 9, so finding one, or exhausting a large part of its space with exact bookkeeping, is evidence of a kind that has not existed before.
Where the method goes next
The search itself is the other product: exact bookkeeping of what was covered, results that anyone can re-verify, and GPU kernels that run in a browser. The same machinery fits sequence and design searches where better objects are used today.
Low-autocorrelation sequences
Finding the ±1 sequence of length N with the cleanest autocorrelation (the LABS problem) is a standard benchmark for quantum and quantum-inspired optimizers. Proven optima stop at N = 66, set in 2016. Each new proven length gives the field ground truth it currently lacks.
Pulse design
The same sequences shape radar and sonar pulses: low autocorrelation means a sharp echo with weak side lobes. Golay complementary pairs, a close cousin of Legendre pairs, also tame signal peaks in OFDM radios.
Covering arrays
A covering array is the smallest set of test cases that exercises every combination of a few settings. Smaller arrays mean fewer tests, and the best known tables improve through exactly this kind of exhaustive, verifiable search.
Screening designs
Plackett–Burman and related designs, built from Hadamard matrices, decide which factors matter in a manufacturing or lab experiment. Standard sizes are covered; unusual run sizes still benefit from new constructions.