
Abstract
A search for an Andrews-Curtis reduction that bounds the total length of the relators is defeated by the bound rather than by its budget, and this paper measures the difference on the 10,115 balanced presentations of the SAIR Andrews-Curtis Challenge pool. Ten presentations whose shortest reduction is known are returned at exactly that length, in 0.4 to 2.6 seconds and 2,028 to 2,456,933 search states, by a search with no length bound at all, ordered instead by the priority L(P) + w d(P) on total relator length L and moves spent d, at w = 12. At w = 4 eight of the ten are exact; at w = 0 the same search returns 32 moves against an optimum of 15. That the bound and not the budget is the defect is then shown directly: on 196 presentations nobody has reduced, a bounded search closed its entire space in 256 to 897,279 states, so no reduction of any of them stays within its starting length, and for 33 none stays within four of it. Three further measurements bound what a search of this family can reach. The priority is at least w d, which caps reachable depth, and w = 12 solves every record of 16 moves or fewer and none of 35 at records 121 to 300. The backward half of a bidirectional search never reads the presentation, a fact one recurring state count, 7,226,201 across eight presentations of one run, makes visible; that permits amortisation and also bounds it, since one precomputed set of 22,000,000 states contained 2 of the 10,115 presentations. Under a tie rule that halves a record’s value for each further team holding it, competence and point value are anti-correlated by construction: 146 held records paid 3.16 points while 1,012 unheld ones were worth about 388. One bounded non-existence statement is reported with its hypotheses stated in full. All code and data are public.
Introduction
A group presentation is balanced when it has as many defining relations as generators. Andrews and Curtis [1] asked whether every balanced presentation of the trivial group can be reduced to the standard presentation of the same rank using only elementary moves on the relators: inverting a relator, multiplying it by another relator, and conjugating it by a generator. Sixty years later the question is open, and the practical form of it is a search problem. Given a balanced presentation, find a sequence of those moves that ends at the standard presentation, and find a short one.
This paper is about how that search should be built, and about what bounds it. It reports measurements over the 10,115 two-generator presentations of the Discovery pool of the SAIR Andrews-Curtis Challenge [8], a public competition in which teams submit reductions and are scored on their length. It makes no claim about the conjecture in either direction. Every reduction quoted below was replayed by the competition’s own reference verifier before it was counted [9].
The central finding is a design error and its correction. A bidirectional search over presentations is naturally written with an admission test: reject any state whose total relator length exceeds the starting length by more than some slack. The test is what makes the state space finite and the search exhaustive inside it, and it is the reason such a search can certify a minimum. It is also the reason the search fails. Figure 1 sets the two cases side by side. On the presentations whose shortest reduction the field already knows, the length falls almost monotonically from the first move, so the admission test costs nothing. On presentations nobody has reduced, a bounded search closes its whole space and finds no reduction at all, which proves that any reduction of them must first make the relators longer, exactly the states the test forbids. No budget corrects a test that has excluded the answer.
The correction is to keep length as the order of the search and discard it as a gate. Section 4 states the priority
f(P) = L(P) + w d(P),
(1)
on the total relator length L(P) of a presentation P and the number of moves d(P) already spent reaching it, with no admission test of any kind. A state that lengthens the relators is then not forbidden but explored late. Section 5 measures what that is worth, and Sections 6 to 11 measure what it does not fix. ### Contributions- A hard bound on total relator length is the dominant design error, and the claim is proved rather than assumed. Replacing the bound with the priority of Equation (1) returns all ten known optima at exactly the optimum, in 0.4 to 2.6 seconds (Section 5). On 196 presentations nobody has reduced, a bounded search exhausted its space at slack 0 in 256 to 897,279 states, so no reduction of any of them stays inside its starting length, and for 33 of them none stays within four of it (Proposition 2).
- The two terms of the priority trade off, provably. Since f ≥ w d, the weight bounds reachable depth. Measured: w = 12 solves every record of 16 or fewer moves and none of 35 at records 121 to 300, while w = 0 reaches those and returns 1,912 moves against a record of 121 (Section 6).
- The backward half of a bidirectional search never reads the presentation. It is therefore shared across every presentation of a given size, which one recurring state count makes visible, and that both permits amortisation and bounds precomputation: one set of 22,000,000 states at length 40 contained 2 of the 10,115 presentations (Section 7).
- Competence and point value are anti-correlated by construction. A record is short and widely shared because it is easy, long and singly held because it is not, so a tie rule that halves a record’s value for each further holder makes everything reachable nearly worthless. Measured: 146 held records paid 3.16 points, while targeting the valuable band inside a fixed competence boundary returned nothing on 16 attempts, 23 attempts and 61 attempts by three different methods (Section 8).
- A bounded non-existence statement, with its hypotheses. For
ac-07351a decision-mode search closed its space at 75,577,713 states of a budget of 150,000,000, so no reduction of length at most 24 exists among the paths its bound admits (Section 9). Section 10 explains why the statement cannot at present be made unconditional, and the reason is the second negative result reported here.
Hypotheses
Four claims organise the experiments. Each could have been contradicted by a measurement, and Section 11.1 returns to each with the evidence.
- H1 (the bound, not the budget). A search that orders by total relator length solves presentations that a search bounding the same quantity does not, at an equal or smaller budget.
- H2 (one setting serves the pool). Some single weight w in Equation (1) is competent across the pool’s range of record lengths.
- H3 (reach, not targeting). Score comes from moving the competence boundary outward, not from choosing targets more carefully inside it.
- H4 (a constant factor buys reach worth having). Storing states more compactly, and so affording more of them, reaches records that pay. The evidence supports H1 and the first half of H3. It contradicts H2 and H4. H3 turns out to be true in its negative direction and false in its positive one: targeting inside the boundary returns nothing, and the one method that moved the boundary outward still scored almost nothing, so reach is necessary and not sufficient. Reporting that split is the point of stating the hypotheses in advance.
Figure 1. Why bounding total relator length is the wrong instrument, in two measured cases. **A** plots the total relator length along the 15-move reduction of `ac-00236` that this work submitted and the competition verified: it never rises above the starting value, so an admission test at slack 0 would have admitted every state of it. That is what the easy cases look like. **B** is `ac-00399`, which no team has reduced. A bidirectional search closed the whole space its bound admits, every state of total length at most 13 + 4, using 897,279 states across its two halves, and its frontiers never met. Any reduction of `ac-00399`, should one exist, therefore leaves the shaded box, and a search that rejects states outside the box cannot find it at any budget. The solid curve in **A** is measured; the dashed curve in **B** is the only thing on this figure that is not, since what lies above the box is precisely what is unknown.
Background
Presentations, moves and the target
Write F for the free group on x and y. A state of the search is an ordered pair P = (r0, r1) of words in F, read as the balanced presentation ⟨ x, y ∣ r0 = 1, r1 = 1 ⟩. Words are freely reduced after every operation, so adjacent inverse letters cancel. Write
L(P) = |r0| + |r1|
for the total relator length, the sum of the two word lengths, and d(P) for the number of moves applied in reaching P from the presentation the search started at.The three Andrews-Curtis moves, each acting on one relator and leaving the other alone, are inversion ri ↦ ri-1, multiplication ri ↦ ri rj± 1 for j ≠ i, and conjugation ri ↦ c ri c-1 for c ∈ {x, x-1, y, y-1}. At rank 2 this gives 14 distinct moves from every state: two inversions, four multiplications and eight conjugations. Each move is invertible, so the state graph is undirected and cycles are everywhere, which matters for every search below.
The target is the ordered pair (x, y), the standard presentation. A sequence arriving at (y, x) has not finished. This is not a pedantic point: an early version of the learned search in Section 11 accepted any two distinct generators as the goal, reported reductions shorter than lengths the field had proved optimal, and failed verification on all ten cases it reported. The reference verifier caught it.
The pool and the competition
The SAIR Andrews-Curtis Challenge [8] is an open competition run by Caltech and the SAIR Foundation, co-organised by Lucas Fagan, Sergei Gukov and Terence Tao. Its Discovery Track publishes 10,115 two-generator balanced presentations and scores submitted reductions of them; a separate Proof Track takes mathematical results. Of the 10,115 presentations, roughly 10,000 come from a random draw and the remainder from the Miller-Schupp family [2]. The pool is not certified to consist of presentations of the trivial group, and Section 10 reports the one necessary condition that can be checked cheaply, together with the measurement that it eliminates nothing here.
Scoring is what makes the pool an object with a geometry rather than a list. On each presentation the k teams tied for the shortest verified reduction each earn
points = 2 1-k,
(2)
and every other team earns nothing [[8]](#ref-8). One team holding a record alone earns 1 point, two tied teams earn 1⁄2 each, three earn 1⁄4 each. A team that matches a record currently held by k teams therefore earns 2-k, since it becomes the (k+1)-th holder: matching a record held alone pays 1⁄2, and matching one held by seven teams pays about 0.008. Beating a record outright pays 1 and drops every previous holder to nothing.Throughout, the record of a presentation means the length of the shortest verified reduction any team holds, and k means the number of teams holding it. Both are read from the competition’s public leaderboard and both move while a campaign runs, which Section 12 treats as a threat to validity.
Verification discipline
Nothing below is counted until the competition’s reference verifier has replayed it [9]. The implementation used here carries its own replay as well, and its move semantics were checked against the reference implementation on 19,222 states with no mismatch. The order matters more than the count: two of the three search bugs found during this work announced themselves as reductions shorter than a proved optimum, which is a signature of a wrong goal test or a wrong move, and an unverified pipeline would have recorded them as results.
Related work
**The conjecture and its presentations.**Andrews and Curtis [1] posed the question and fixed the move set searched over here. Miller and Schupp [2] give the family of balanced presentations of the trivial group that most computational work takes as its benchmark, and part of the pool of Section 2.2 is drawn from it. Akbulut and Kirby [3] produced the presentations that remain the best known candidate counterexamples, and they serve here as a correctness check rather than a target: the second of that family is reduced by the engine used below in under a second, and the third is not reached at all, which is the expected behaviour and a useful early signal that a search is wired correctly. **Search over presentations.**The two halves of the search used here are standard and neither is claimed as new. Pohl [6] introduced bidirectional search, expanding from the start and from the goal at once, which is what makes Section 7 possible; Pohl [5] introduced the weighting of an estimate against the cost already paid, which Equation (1) is an instance of with the roles reversed, since here it is the cost already paid that is weighted against a structural quantity. Korf [7] introduced depth-first iterative-deepening, whose memory in the depth rather than in the number of states visited is what Section 9 needs in order to close a space rather than merely to search it. **Learned policies on this problem.**Shehper et al. [4] study Andrews-Curtis search as a case study in what makes a problem hard for reinforcement learning, and report that a greedy baseline already solves much of the Miller-Schupp family. That result is the yardstick for the present measurements in two ways. It is why the failure of every method here on the long-record part of the pool is worth reporting rather than assuming: a family on which greedy succeeds and this pool, on which it does not, differ, and Section 2.2 names the difference. It is also the reference for the direction Section 11 probes and does not reach, since the least-squares estimator fitted there is the cheapest possible stand-in for a trained policy. **Positioning within the author’s prior work.**Several strands of the author’s earlier work bear on the design choices made here, and each is named for something specific it contributes. The decomposition in Section 7, which splits one search into a half that depends on the presentation and a half that does not, is the move Thakur et al. [19] makes on images: separate a problem into components with different behaviour before acting on any of them, because the components are cheap in different ways. What the separated half then becomes is an index built once and queried many times, which is what a quadtree is for [20], and Section 7 measures exactly how little of a 10,115-presentation pool one such index reaches. The two halves also advance at different rates and have to be kept in step, since expanding whichever frontier is smaller is what keeps a bidirectional search exact; that bookkeeping between two independently advancing processes is the problem Thakur and Satish [21] treats in a distributed setting. Equation (1) combines two criteria under a single weight and behaves differently at each setting of it, which is the design Thakur et al. [15] examines for graded inference, and Section 6 measures the consequence that no setting serves the whole pool. Two objectives in fixed opposition are also the shape of the adversarial training Thakur and Satish [17] surveys, with the instructive difference that there the balance point is learned while here it is a parameter that measurement shows has no good value. The estimator of Section 11 is an ordinary least-squares fit over hand-built features, in the supervised setting Thakur and Konde [16] lays out, and its first version failed in a way that belongs to the training distribution rather than to the model: trained on every reduction the campaign had ever produced, including its own 1,912-move wanderings, it learned the search’s inefficiency and scored worse than total length alone. A pipeline that assigns labels without ever training on examples of the target class, as Thakur and Talele [14] does, cannot fail this way, and the contrast is what led to the correction. The decision-mode search of Section 9 distinguishes three outcomes rather than two, answering yes, no, or undecided, and declining to answer when the evidence is absent is the response Thakur and Satish [18] adopts for inputs from outside a method’s domain.
Two papers in this programme measure adjacent boundaries. The companion study of degree-24 Galois group identification [11] runs under the same tie rule of Equation (2) and reports the same anti-correlation between what a method can reach and what reaching it pays, which suggests the effect belongs to the scoring rule rather than to either problem; Section 8 states the mechanism in general form. The companion study of neural modular arithmetic [12] finds the binding constraint in the structure of the task rather than in the size of the model or the budget, and reports that a learned representation covers only the range its training touched. Both findings recur here, in Section 11 and in Section 8 respectively, on a problem with no learning in it at all.
Length as an order, not a wall
The two searches
Both searches below are bidirectional, expanding from the presentation and from the standard presentation at once and stopping when the frontiers meet. They differ in one line.
Definition 1 (Bounded search). Fix a slack s ≥ 0 and set the bound B = L(P0) + s for the starting presentation P0. The bounded search expands states in order of increasing depth and rejects any state P with L(P) > B. It halts when the frontiers meet, when the state space inside the bound is exhausted, or when its budget of states is spent.
Definition 2 (Priority search). Fix a weight w ≥ 0. The priority search holds its frontier in a queue keyed on f(P) = L(P) + w d(P) and expands a state of least key. There is no admission test: the only bound is the fixed buffer that holds a word, 42 letters in the implementation used here. The bounded search enumerates a finite space and can therefore certify that no reduction exists inside it, which is what makes the measurements in Section 5 and Proposition 2 possible. The priority search certifies nothing and reaches further. Neither dominates the other, and the point of separating them is that their failures are different in kind.
What the bound does that the order does not
Proposition 1. Let P0 be a presentation, s ≥ 0 a slack and B = L(P0) + s.
(Exclusion.) If every reduction of P0 passes through some state P with L(P) > B, then the bounded search at slack s returns no reduction, at any budget, and terminates by exhausting its space.
(Postponement.) For w > 0 the priority search excludes no state its word buffer can hold: if Q is reachable from P0 by a sequence of d moves whose states all satisfy L ≤ M, then Q is expanded no later than the point at which the key reaches M + w d.
(Depth bound.) Since f(P) ≥ w d(P), every state the priority search expands before its key reaches F satisfies d(P) ≤ F/w. A reduction longer than F/w moves is therefore unreachable within a budget that carries the key only to F.
Proof. For (i), the bounded search generates only states with L ≤ B, and by hypothesis no reduction consists of such states alone. Its space is finite because there are finitely many freely reduced pairs of words with L ≤ B, so with a sufficient budget it terminates by exhaustion. For (ii), let P0 = Q0, Q1, …, Qd = Q be the sequence. Each Qi has f(Qi) ≤ M + w i ≤ M + w d, and a queue that expands a state of least key first expands every state of key at most M + w d before any state of greater key, so the sequence is expanded in order. For (iii), L(P) ≥ 0 gives f(P) ≥ w d(P) at once. □ None of the three parts is deep. They are stated because they are different in kind, and because the difference is what the measurements below are about. Part (i) says the bounded search can fail for a reason no budget touches. Part (ii) says the priority search cannot fail that way. Part (iii) says it fails another way instead, by making deep reductions unreachable in proportion to w, which is Section 6. The weight therefore buys exactness with reach, and the exchange rate is the subject of the rest of this paper. **What this means.**A bound and an ordering look like the same thing seen from different angles, and they are not. Bounding total relator length decides in advance that the answer lies in a box. Ordering by total relator length decides only what to look at first. When the answer is in the box, the bound is the better instrument, because it also proves the answer is shortest. When the answer is not in the box, no amount of computation inside the box will say so in a way that helps, and the next section shows this is not hypothetical.
Reductions must go uphill, and how far is measurable
The claim that Andrews-Curtis reductions lengthen the relators before collapsing them is usually offered as an explanation of why greedy descent on L stalls. On this pool it can be measured, because the bounded search is exhaustive inside its bound.
Proposition 2. Let P0 be a presentation for which the bounded search at slack s terminates by exhausting its space without finding the standard presentation. Then every reduction of P0, if any exists, contains a state P with L(P) > L(P0) + s.
Proof. Write A for the set of states reachable from P0 through states of total length at most L(P0) + s, and Z for the set reachable from the standard presentation through such states. Exhaustion without the frontiers meeting says that both sets were enumerated in full and that they are disjoint. Suppose some reduction of P0 had all its states of total length at most L(P0) + s. Each state on it lies in A, by the prefix of the reduction, and in Z, by the suffix read backwards, which is a sequence of moves because every move is invertible. Then A ∩ Z ≠ ∅, contradicting disjointness. Both sets are finite because finitely many freely reduced pairs of words have total length at most L(P0) + s, so exhaustion is reachable with a sufficient budget. □ Measured on the presentations no team has reduced, against a budget of 5,000,000 states per half:
Remark 3. The visited set is a table of 64-bit hashes, so a collision can cause a state to be skipped, and the exhaustion claims hold modulo that. At 106 states the probability that any pair of distinct states collides is about 3 × 10-8.
**What this means.**The picture in Figure 1 is not a metaphor. For 196 specific presentations of the pool, the total relator length must increase at some point along any reduction, and for 33 of them it must increase by more than four. A search that forbids those states has removed the answer from its own space, which is what Proposition 1(i) says and what the exhaustion counts confirm. Two qualifications keep the statement honest. The pool is not certified to present the trivial group, so a presentation with no reduction at all satisfies the conclusion vacuously; and the bound at slack 12 and beyond is where the space stops closing, so the method that proves the statement runs out exactly where the statement would become most interesting.
Ten known optima
The ten presentations in Table 1 are the reachable end of the pool: each has a record that this work matched and that the field has converged on, so the optimum is known independently of any search reported here. They are the only place in this pool where a search can be measured against ground truth rather than against a leaderboard.
| Presentation | Optimum | w = 0 | w = 1 | w = 4 | w = 12 |
|---|---|---|---|---|---|
ac-00236 | 15 | 32 | 16 | 15 | 15 |
ac-00343 | 15 | 140 | 17 | 15 | 15 |
ac-00488 | 14 | 129 | 15 | 14 | 14 |
ac-00742 | 10 | 13 | 11 | 10 | 10 |
ac-00807 | 14 | 75 | 17 | 14 | 14 |
ac-00894 | 14 | 82 | 17 | 15 | 14 |
ac-01143 | 16 | 37 | 17 | 17 | 16 |
ac-01411 | 11 | 21 | 16 | 11 | 11 |
ac-01586 | 13 | 49 | 15 | 13 | 13 |
ac-01635 | 8 | 10 | 10 | 8 | 8 |
| Exact | 0 / 10 | 0 / 10 | 8 / 10 | 10 / 10 | |
| States | 176 to 4,710 | 177 to 858 | 1,118 to 80,046 | 2,028 to 2,456,933 | |
| Seconds | 0.4 to 0.6 | 0.3 | 0.3 to 0.4 | 0.4 to 2.6 |
Table 1. The priority search on ten presentations of known optimum, at four settings of the weight w in Equation (1). Each entry is the length of the reduction returned, and every one was replayed and verified. The lower panel gives the range of states expanded and of wall-clock seconds across the ten. Reading down a column shows what the weight buys; reading across a row shows what it costs. The bounded search of Section 4 also finds these optima, and needs millions of states and 5 to 25 seconds each to do it.
Three readings follow, and the third is the one that matters. **The weight buys exactness and is paid for in states.**At w = 0 the queue is ordered by total length alone, and the reductions returned are far from minimal: 32 moves against an optimum of 15, 140 against 15, 129 against 14. The search is cheap, 176 to 4,710 states, and it is answering a different question, namely which state is shortest, not which reduction is. At w = 1 every reduction is within five moves of the optimum and none is equal to it. At w = 4 eight of the ten are exact and the two misses are one move over, at 1,118 to 80,046 states. At w = 12 all ten are exact, at 2,028 to 2,456,933 states. Exactness costs roughly three orders of magnitude in states across that range, and the order of the trade is what Section 8 prices. **The claim at w = 4 is eight of ten, not ten.**An earlier record of this work reported the w = 4 column as the headline. It is eight of ten, and the two misses, `ac-00894` and `ac-01143`, are the two longest optima in the set. Only w = 12 reaches all ten, and it does so at up to thirty times the states. Stating the weaker figure for the cheaper setting is what makes the trade visible. **The bounded search reaches the same optima and costs far more.**On these ten the bounded search is not defeated: it finds every optimum, which is how they are known. It needs millions of states and 5 to 25 seconds for each, against thousands of states and under a second for the priority search at w = 4. On this band the correction is an efficiency, and by Proposition 2 the band where it is more than an efficiency is the band where the field's records are, and where nothing reported here scores. **Widening the bound is not a substitute for removing it.**Two measurements say so. On `ac-03055`, whose record is 91, the bounded search at slack 2 returns 95 moves and at slack 4 returns nothing at all: the space inside a wider box grows faster than the budget covers, so widening loses a reduction it had found. Across records 18 to 22 at a fixed 12,000,000 states per half, slack 4 found 23 presentations and scored on 18, slack 8 scored on 11, and slack 12 scored on 9, while widening to slack 16 lost presentations that slack 12 had found. The bound has no monotone setting, which is the practical face of Proposition 1(i). ## The band a single weight is competent on Proposition 1(iii) bounds the depth the priority search can reach by F/w, so a large weight and a long reduction are incompatible. The pool makes that concrete, because its records span two orders of magnitude. | Records | Attempted | Scored | What the search returns | |---|---:|---:|---| | 8 to 16 | 10 | 10 | the optimum, exactly | | 17 to 26 | 22 | 4 | the optimum on four, at k = 6, 6, 9, 13 | | 27 to 40 | 21 | 0 | nothing | | 20 to 60 | 36 | 2 | the optimum on two, at k = 6, 8 | | 121 to 300 | 35 | 0 | nothing at w = 12; about 1,912 moves at w = 0 | | 301 and up | 17 | 0 | nothing at w = 12; about 3,742 moves at w = 0 | | unreduced | 28 | 0 | nothing |Table 2. The priority search at w = 12 across the pool's record bands, with the number of teams k holding each record it matched. Competence ends near a record of 18 and does not resume. The last two rows give what w = 0 returns on the same presentations, which is a reduction of roughly fifteen and twelve times the record length: reachable, and far too long to score.
Table 2 is the measurement. At w = 12 every record of 16 moves or fewer is matched exactly, four of 22 presentations at records 17 to 26 are matched, and nothing at all is returned at records 27 and above, across 21 attempts at records 27 to 40, 35 at records 121 to 300, 17 above 301 and 28 on presentations no team has reduced. At w = 0 the deep presentations are reachable and the reductions are useless: 1,912 moves against a record of 121 and 3,742 against a record of 301. Intermediate weights do neither well.Shortening does not rescue a long reduction. Replacing detours in the 1,912-move path converges at once and then stops, at 415 moves, then 396, then 396 again, which is still more than three times the record; on reductions that are already short the same procedure gains about 2%, taking 106 moves to 104 and 119 to 117, and a deeper search for detours buys one further move for six times the time.
Figure 2. The exchange the two terms of Equation (1) make, on the ten presentations of Table 1. The solid curve is how far the reduction returned exceeds the known optimum, averaged over the ten, on the left axis: 45.8 moves at w = 0, 2.1 at w = 1, 0.2 at w = 4 and 0 at w = 12. The dashed curve is the states the most expensive of the ten cost, on the right logarithmic axis. Exactness is bought at three orders of magnitude in states, and w = 1 is the cheapest setting rather than w = 0, because charging a little for depth stops the queue wandering. What the figure cannot show is the other end of the exchange, since at w = 12 the presentations with long records return nothing at all; Table 2 gives that side.
**What this means.**The weight is not a parameter awaiting a better value. It selects a band of record lengths, and moving the band does not widen it. Figure 2 prices one end of the exchange, where exactness costs three orders of magnitude in states, and Table 2 shows the other, where the setting that buys exactness returns nothing at all past a record of about 26. A pool whose records run from 8 to over 1,000 cannot be served by one setting of one weight, and the measurement that would have contradicted H2, a weight competent at both ends, was looked for at four settings and not found.
The backward half never reads the presentation
A bidirectional search here is asymmetric in a way that is easy to miss. The forward half expands from the presentation under test. The backward half expands from the standard presentation under an admission rule, L ≤ B, that mentions the presentation only through the number B. Two presentations of the same total length therefore give the backward half identical work, which Figure 3 draws and the proposition below states.
Proposition 4. Let the backward half expand from the target T under an admission rule that depends only on the state and on a bound B. Then the set of states it enumerates, together with each state’s exact distance from T, depends only on (T, B) and not on the presentation the forward half started from. If N presentations share a value of B, the total backward work over all N is one N-th of the work N independent searches perform.
Proof. Induct on the backward layers. Layer 0 is {T}. Layer i + 1 is the set of admissible states one move from layer i and not already enumerated, and both the move set and the admission rule are functions of the state and B alone. No layer mentions the starting presentation, so neither does the union or the distance labelling. The second claim follows by building the set once and reusing it. □ The proof is a formality; the point is that the waste it describes was invisible until the state counts gave it away. In one run the same total, 7,226,201 states, was reported for eight distinct presentations, with records 34, 41, 42, 44, 46, 48, 49 and 50; in another run the same total appeared for four more. A failing bounded search ends by exhausting its space, and its total is therefore the size of that space, which Proposition 3 says is shared. The recurrence is a fingerprint of the redundancy, not a coincidence. The same signature appears at wider bounds: five presentations at slack 12 all reported 7,609,129 states and five at slack 20 all reported 7,818,033.
Figure 3. The asymmetry Proposition 3 describes. The forward half expands from the presentation under test and is specific to it. The backward half expands from the standard presentation under an admission rule that names the presentation only through the length bound, so it rebuilds the same set of states, with the same distances, for every presentation of a given size. In one run that set was rebuilt from scratch for eight presentations in succession, each reporting the same total of 7,226,201 states. Building it once turns a cost per presentation into a cost per bound, and Table 3 measures what the shared set then reaches.
Building the backward set once per bound and sweeping every presentation of that size against it is what `ball_search.py` in the artefact does. It reproduces 8 of 8 known optima exactly, from a set of 4,000,000 states built in 4 seconds, and it reduces the cost of one presentation from about 20 seconds to between 0.2 and 12. | | Bound on L | States | Result | |---|---:|---:|---:| | Validation set built once | size + 2 | 4,000,000 | 8 of 8 known optima reproduced | | One set for the whole pool | 40 | 22,000,000 | 2 of 10,115 presentations inside | | Depth the wide set reaches | 40 | 22,000,000 | 8 to 10 moves | | Depth the pool needs | | | 20 to 130 moves |Table 3. What precomputing the backward set buys, and what bounds it. Built at a bound tight enough to reach deep, the set is specific to presentations of one size and reproduces their optima. Built wide enough to contain the whole pool, the same budget of states reaches 8 to 10 moves from the standard presentation, while the pool lies 20 to 130 moves away. The 22,000,000-state set took 19 seconds to build and contained 2 of the 10,115 presentations, both of which it matched rather than beat.
Table 3 gives the bound on the idea. One set of 22,000,000 states at bound 40, built in 19 seconds, contained 2 of the 10,115 presentations. The reason is the same lever as everywhere else in this paper. At a tight bound most moves break the bound and are rejected, branching is low and the set reaches deep; at bound 40 almost every move is admissible, branching is wide, and 22,000,000 states buy 8 to 10 moves of depth against the 20 to 130 the pool sits away. No single bound is both wide enough to contain the pool and tight enough to reach it. **What this means.**Proposition 3 is a licence to amortise and a limit on what amortisation is worth. It converts a per-presentation cost into a per-size cost, which is a real saving on a pool with thousands of presentations of the same size, and it also says that the shared object is a ball around the standard presentation whose radius in moves grows very slowly in its size in states. Precomputation reaches further by narrowing, and narrowing is what excludes the pool. ## Competence and point value are anti-correlated by construction This section states the paper's structural result. It is about the pool under Equation (2), not about any particular solver, and it explains a measurement no amount of tuning changed. ### The mechanismProposition 5. Order the presentations of a pool by a difficulty parameter and suppose two empirical conditions hold.
(Monotone competence.) The set C of presentations a given solver matches at the optimum is downward closed in difficulty.
(Monotone crowding.) The number of teams k holding a record is non-increasing in difficulty, so every presentation in C is held by at least κ = minP ∈ C k(P) teams. Then under Equation (2) the total score available to that solver is at most |C| · 2-κ, whatever presentations inside C it chooses to attempt, and the bound is unchanged by any reordering of its effort. Improving it requires enlarging C.
Proof. A match on a presentation held by k teams pays 2-k, which is non-increasing in k and therefore at most 2-κ for every P ∈ C by condition (ii). Summing over C gives the bound. Nothing in the argument refers to the order in which presentations are attempted. □ Both conditions are empirical and both are measured here. Table 4 measures condition (ii) directly: the number of teams holding a record falls as the record lengthens, from ten teams on a record of 8 to two teams at records reaching 48. Condition (i) is what Table 2 measures, with the one exception Section 11 reports.
| Teams k holding the record | Presentations | Median record |
|---|---|---|
| 10 | 1 | 8 |
| 8 | 48 | 15 |
| 3 | 19 | 26 |
| 2 | 20 | 26, longest 48 |
Table 4. Crowding against record length, over the held presentations at one snapshot of the leaderboard; the four bands recorded cover 88 of them. A record is short and widely shared, or long and held by few. This is the empirical content of condition (ii) of Proposition 4, and it is a property of the pool and the field rather than of any solver.
The measurement
| Target | Teams k | A match pays | Measured |
|---|---|---|---|
| records 18 and below | 6 to 13 | 0.016 to 0.0001 | all but one already held |
| record 19 | 6 | 0.016 | reached |
| records 19 to 30 | 1 or 2 | 0.50 or 0.25 | 0 of 16 |
| records 19 to 60 | 1 or 2 | 0.50 or 0.25 | 0 of 23 |
| records 27 to 40 | any | 0 of 21 | |
| records 121 to 300 | 1, on 2,291 of 2,303 | 0.50 | 0 of 35 |
| records 301 and up | 1, on 1,350 of 1,353 | 0.50 | 0 of 17 |
| improving a held record | 10 | 0 of 61, and 8 proved optimal |
Table 5. Reach against value. Every target the search reaches pays at most 0.016 and usually far less; every target worth 0.25 or more is unreached, across 16, 23, 21, 35 and 17 attempts by the search of Section 4 at w = 12 with 12,000,000 states per half. The last row is the other direction: on a presentation whose record of 8 is shared ten ways, walking the bound from slack 1 to slack 8 returns 8 every time, which witnesses optimality and confirms that a heavily shared record is evidence of a problem already solved rather than of an opportunity.
Table 5 is the result, and Figure 4 is the same thing as a picture. Inside the competence boundary a match pays at most 0.016 and the search reaches reliably. Outside it a match pays 0.25 to 0.50 and the search returns nothing, on 16 attempts at records 19 to 30, 23 at records 19 to 60, 21 at records 27 to 40, 35 at records 121 to 300 and 17 above 301. In records 19 to 30 alone the pool holds 73 unreduced presentations at k = 1 and 45 at k = 2, which is about 48 points, all of it outside the boundary. At a later snapshot the same count over records 21 to 45 was 1,012 presentations worth about 388 points. Against that, the 146 records this work held at the end of the campaign were worth 3.1617 points in total, and none of them was held outright.Figure 4. The two curves of Proposition 4, measured. The solid curve is the fraction of attempted presentations the search matched exactly, on the left axis; the dashed curve is what matching one pays under Equation (2), on the right logarithmic axis, at the number of holders Table 4 records for each band. They cross just outside the competence boundary, which is why 146 held records were worth 3.16 points while 1,012 unreached ones were worth about 388. Moving the boundary right is the only operation that changes the picture; choosing targets inside it cannot.
Why a constant-factor improvement does not help
The competence boundary is bounded by states, and states by memory, so the obvious lever is to store states more compactly. Letters are drawn from four values and need two bits each where the implementation spends a byte, which takes a state from 103 bytes to 37, a factor of 2.8. Table 6 prices the lever before building it.
| Cost of exact reach | Value in the bands beyond it | |||
|---|---|---|---|---|
| Record | States | Band | Presentations at k ≤ 2 | Points |
| 8 | 2,028 | records 19 to 21 | 2 | 0.8 |
| 14 | 172,372 | records 19 to 23 | 7 | 2.5 |
| 16 | 2,456,933 | records 19 to 25 | 19 | 7.8 |
| 19 | 12,812,195 |
Table 6. Measured cost of exactness against record length, at w = 12, beside the value that lies just outside reach. Each additional move of record costs about 1.7 times as many states, so a factor of 2.8 in the budget extends reach by roughly 2.2 moves, from about 18 to about 21. That buys the first band alone, worth 0.8 points, while the bands behind it grow faster than the budget can follow. Reach grows logarithmically in the budget and value sits exponentially further out, which is why no constant-factor gain closes the gap.
Figure 5. The cost of one more move of exact reach, on a logarithmic vertical axis, from the four measured points in Table 6. The slope is about 1.7 times the states per move of record, so the budget must grow exponentially in the reach it buys. The dashed extension is what a 2.8-fold gain in states per byte would deliver: about 2.2 further moves of record, and under one point of value by Table 6. This is why the negative result of Section 8 is structural rather than a matter of engineering.
**What this means.**The statement is stronger than saying a solver is too weak. A solver that is too weak can be improved. Here the pool and the scoring rule together ensure that the presentations a solver can reach are the presentations everybody has reached, because both facts follow from the same underlying quantity, how hard the presentation is. Under Equation (2) the value of a record is decided by how many teams share it, so value is anti-correlated with reachability by construction, and Proposition 4 bounds what any target selection inside a fixed competence boundary can earn. The only operation that changes the bound is enlarging the competence set, and Figure 5 prices that in states.
Asking the decision question, and one bounded non-existence result
Every search above optimises: it returns the shortest reduction it can find, and spends most of its budget on lengths that could not have scored. Only one question pays, and it is binary. Does a reduction of at most the record length exist? Starting an iterative-deepening search [7] with its bound at the record asks exactly that, with memory in the depth rather than in the number of states, so the budget stops being a memory budget.
| Presentation | Record | States | Outcome |
|---|---|---|---|
ac-07351 | 24 | 75,577,713 | space closed, no reduction of length 24 or less |
ac-06403 | 22 | 150,000,054 | budget spent, undecided |
ac-02353 | 24 | 150,000,093 | budget spent, undecided |
ac-03474 | 24 | 150,181,843 | budget spent, undecided |
ac-01629 | 24 | 150,000,054 | budget spent, undecided |
ac-03799 | 25 | 150,000,113 | budget spent, undecided |
ac-07188 | 25 | 150,000,100 | budget spent, undecided |
ac-00043 | 25 | 150,000,090 | budget spent, undecided |
Table 7. Decision-mode iterative deepening with the bound started at the record, on eight unreduced presentations held by at most two teams, against a budget of 150,000,000 states each. Seven spent the budget. The first closed its space at half the budget, which is the difference between not finding a reduction and there not being one to find.
Table 7 gives the run. Seven of the eight presentations consumed the whole budget without deciding anything. The eighth terminated by closing its space. > **Proposition 6.** Let B be a bound on reduction length, W a bound on the length of a single > relator, and h a non-negative state function used with a weight ω in > [0, 1]. Consider the depth-first search that, from a presentation > P0, enumerates every sequence of moves whose states satisfy > |r0| ≤ W and |r1| ≤ W and whose depth g satisfies > g + ω h ≤ B, rejecting any state that repeats an ancestor. If it > terminates without reaching the target and without exhausting its budget of > states, then no reduction of P0 of length at most B exists among the > sequences it admits. If in addition h is admissible, meaning h(P) never > exceeds the true number of moves from P to the target, then no reduction of > P0 of length at most B exists within the relator bound W at all.Proof. The first claim is the definition of termination by exhaustion: the enumeration is over the admitted sequences, the ancestor test removes only sequences with a repeated state, which cannot be shortest, and termination without a hit means no admitted sequence reaches the target. For the second, suppose a reduction of length m ≤ B exists with all relators within W. At each of its states the remaining distance to the target is at most m - g, so admissibility gives g + ω h ≤ g + ω (m - g) ≤ g + (m - g) = m ≤ B, using ω ≤ 1 and m ≥ g. Every state of that reduction is therefore admitted, and the search would have found it. □
**The measured instance.**For ac-07351, whose record is 24,
with B = 24, W = 42 letters, h the least-squares estimate of
Section 11 and ω = 1, the search closed at 75,577,713
states against a budget of 150,000,000. By the first half of
Proposition 5, no reduction of ac-07351 of length at
most 24 exists among the sequences that bound admits.
**What this establishes, and what it does not.**Three qualifications
belong with the statement, and the second is the substantive one.
First, the relator bound is a hypothesis, not an artefact to be ignored. The statement concerns reductions whose relators stay within 42 letters, which is the buffer the implementation holds. The pool’s longest presentation totals 40 letters and only conjugation can grow a word past a bound, and by at most 2, which is where 42 comes from.
Second, h is a least-squares fit over nine word statistics, and nothing proves it admissible; Section 11 reports that it overestimates on some states, which is why it removes the optimality guarantee of the search that uses it. The unconditional statement in Proposition 5 therefore does not apply. What is established is non-existence within the admitted region, which is a weaker claim than non-existence, and the honest form of the result is the conditional one. An admissible h would close the gap, and Section 10 reports the only admissible estimate available on this problem and why it cannot serve: its median value over the pool is 5, where a bound of 24 would need something near 24 to prune anything at all. Without a pruning estimate the space at depth 24 is around 1324 sequences, so enumerating it unaided is not an option.
Third, the transposition filter compares full 64-bit hashes, so a collision could suppress a branch. Over 75,577,713 states the probability that any two distinct states collide is about 2 × 10-4.
What survives all three is the distinction the table was run to draw. Seven presentations returned nothing because the budget ran out, and one returned nothing because there was nothing to return inside its bound. At scale this would partition the pool into presentations provably out of reach at a given length and presentations merely unreached, which is a sharper object than a leaderboard position. It also does not score: this is the fifth search architecture in this work to concentrate its budget on the question that pays and change nothing about the result.
Two negatives that bound the approach
The abelianisation test is sound and empty
A balanced presentation of the trivial group has an exponent-sum matrix of determinant ± 1. Writing eij for the exponent sum of generator j in relator i, the matrix (eij) is invariant under conjugation, negates a row under inversion, and adds or subtracts one row from another under multiplication, so its determinant is preserved up to sign, and the standard presentation has determinant 1. Any presentation whose exponent-sum determinant differs from ± 1 therefore admits no reduction.
Deciding a presentation’s fate from a deterministic structural invariant rather than from a search is the approach Thakur [10] takes to classification, and it is the right first move here because the invariant costs one pass over two words. Measured on the pool: 0 of the 7,266 presentations that some team has reduced violate the condition, which confirms the test, and all 2,849 that no team has reduced already satisfy it. The organisers evidently pre-filtered the draw. The test is sound, it is cheap, and on this pool it eliminates nothing.
The admissible lower bound is far too weak
The same matrix yields an admissible lower bound on the number of moves, since
each move changes it in one of three restricted ways. Built over 24,080
matrices, with admissibility verified on 6,482 move applications and no
violation, its median value is 5 and its maximum is 13, while the pool’s records
have a median in the band from 61 to 120 moves. It never reaches the record on
any presentation a team has reduced. A bound of 5 prunes nothing in a search at
depth 15, let alone at depth 24.
**What this means.**The two negatives interlock with the result of
Section 9, and that is why they are reported. A bounded
non-existence statement needs an admissible estimate to become unconditional.
The only admissible estimate available here is the exponent-sum bound, and it is
too weak by a factor of about five to prune at the depths that matter. The
estimate that does prune, and that closed the space on ac-07351, is a
fit with no admissibility guarantee. Closing that gap, by finding an admissible
invariant strong enough to prune at depth 20 or more, would convert a
conditional statement into a theorem and would do more for this problem than any
further tuning of the searches above.
What a learned estimate changes, and what it does not
Shehper et al. [4] point to a learned search policy as the method that makes progress here. Training one needs hardware this work did not have, so the cheapest possible stand-in was measured instead: an ordinary least-squares fit of the distance to the standard presentation, over nine hand-built word statistics, on states drawn from reductions already held, where the true remaining distance is known exactly.
| Estimate of the distance to the target | Mean error | Median error |
|---|---|---|
| total relator length L(P) alone | 5.6 | 4.0 |
| least squares, fitted on record-length reductions | 3.0 | 1.9 |
| least squares, fitted on every reduction held | 42.1 |
Table 8. The fitted estimate against total relator length, in moves. The third row is the first attempt and the reason the second exists: trained on every reduction the campaign had produced, including its own 1,912-move paths, the fit learned the search's inefficiency rather than the geometry of the problem, and scored worse than the single feature it was meant to improve on, which gave 38.1 on the same comparison. Restricting the training set to reductions at or below the current record fixed it.
Table 8 reports the fit. The estimate is better than total length by a factor of nearly two in mean error, and its weights are readable: relator imbalance and maximum relator length raise the estimate, exponent-sum mass lowers it. Used to order a search, it buys about twenty times fewer states and loses exactness, reproducing 3 of the 10 known optima at weight 1 where the priority search at w = 12 reproduces 10.That looked like a reason to discard it, and the judgement was wrong on the band that matters. On unreduced presentations held by at most two teams at records 19 to 60, the priority search at w = 12 found nothing on 23 attempts, while the fitted estimate at weight 3 found reductions for 34 of 222. Table 9 reports what happened next.
| Weight on the estimate | Found | Scored | |
|---|---|---|---|
| 3 | 34 of 222 | 1 | reaches, and overshoots the record by 5 to 18 moves |
| 1 | 4 of 21 | 1 | the same presentation |
| 0.5 | 0 of 19 | 0 | nearly admissible, and reaches nothing |
Table 9. The reach and quality trade again, in a different search. A high weight on the fitted estimate reaches presentations the priority search of Section 4 cannot, and returns reductions too long to score. A low weight restores exactness and loses the reach. No setting does both, which is the shape Figure 2 and Table 2 record for the priority search, and by Proposition 1(iii) for the same reason.
Removing the memory bound did not change the outcome either. Iterative deepening on the same estimate keeps only the current path, so it searched 200,000,000 states where a stored search on the same machine holds 12,000,000, and returned nothing on 17 unreduced presentations at records 19 to 30, several of them consuming the entire budget in 206 seconds. The memory bound was real, its removal was worth building, and the band still did not open. | Architecture | Result on unreduced presentations at k ≤ 2, records 21 to 45 | |---|---| | bounded bidirectional | 0 | | priority search, w = 12 | 0 of 23 | | weighted search on the fitted estimate | reaches 17% to 27%, 0 scoring | | iterative deepening, 200,000,000 states | 0 of 17 | | decision mode, bound started at the record | 0 of 8, and one space closed |Table 10. Five architectures against the part of the pool that carries the value, about 1,012 presentations worth roughly 388 points at the snapshot measured. One of them reaches, none of them scores, and the reductions it reaches with land 5 to 18 moves over the record. Nothing converts them: not detour shortening, not walking the bound upward, not a lower weight, not a deeper budget.
**What this means.**Table 10 is the summary of the programme. Reach and exactness are traded by every architecture measured here, at every setting, and the pool places the records that pay on the far side of the trade. A fitted linear estimate moves the boundary and does not change the outcome, which is evidence about the class of method rather than about the fit: the useful policy is evidently not linear in simple word statistics, and the direction Shehper et al. [4] identify remains the relevant one.
The hypotheses
The four claims of Section 1.2 were fixed before the measurements reported above, and three of the four came out differently from the way the design in use assumed.
H1 holds. The priority search returns all ten known optima at 2,028 to 2,456,933 states and 0.4 to 2.6 seconds where the bounded search needs millions of states and 5 to 25 seconds, and on 196 unreduced presentations the bounded search is excluded from the answer rather than short of budget (Proposition 2).
H2 fails. Four settings of w were measured across six record bands, and each setting is competent on a band: w = 12 solves every record of 16 or below and none of 35 at records 121 to 300, while w = 0 reaches those and returns 1,912 and 3,742 moves against records of 121 and 301. Proposition 1(iii) says why, and the explanation preceded the measurement.
H3 splits. Its negative half holds: targeting inside a fixed competence boundary returned nothing on 16 attempts at the valuable band, nothing on 23, and nothing on 61 attempts to improve a record already held, 8 of which the search proved optimal. Its positive half fails: the one method that moved the boundary outward, reaching 34 of 222 presentations at k ≤ 2, scored on one of them. Reach is necessary and it is not sufficient.
H4 fails, and was priced rather than built. Exact reach costs about 1.7 times as many states per additional move of record (Table 6), so the 2.8-fold gain available from packing states buys about 2.2 moves of reach and under one point of value. No constant-factor gain closes a gap that sits exponentially further out.
Limitations and threats to validity
**What the paper does not claim.**Nothing here bears on the Andrews-Curtis conjecture in either direction. The non-existence statement of Section 9 is about one presentation, one length bound and one relator bound, and it is conditional on the pruning estimate as Proposition 5 makes explicit. The uphill statements of Proposition 2 are unconditional given exhaustion, and they say only that a reduction must lengthen the relators, not that one exists. **The pool is not certified.**The 10,115 presentations are not accompanied by proofs that they present the trivial group, and Section 10 shows the one cheap necessary condition eliminates none of them. Every statement of the form ``no reduction with property X exists’’ is therefore compatible with no reduction existing at all, and is stated that way. **A moving target.**Records and holder counts are read from a live leaderboard and both moved throughout. Two presentations in this paper appear with different records in different runs, because the record changed between them. Every count in Tables 4 and 5 is a snapshot, and the conclusions that depend on them are the orderings rather than the absolute values. Proposition 4 is stated so that it survives this: it needs crowding to be monotone in difficulty, which the snapshots agree on, and not any particular value of k. **One machine.**Every measurement comes from a single consumer machine, and several of the negative results are budget-limited at levels a larger machine would exceed. This weakens the negatives that rest on a budget, namely the undecided rows of Table 7 and the zero rows of Table 2. It does not weaken the results that rest on exhaustion, which are budget-independent by construction, nor Proposition 4, whose bound is about the scoring rule. Table 6 converts the machine limit into records of reach, so the effect of a larger budget can be read off rather than guessed: a hundredfold budget buys about nine moves of record. **Sample sizes.**The exactness result rests on ten presentations, which are all the presentations in this pool whose optimum is independently known at a length the search can reach. The band measurements rest on 10 to 36 attempts each. These are small samples and the intervals around them are wide; what they support is the direction and the ordering, which are consistent across every band and every architecture, rather than the second digit of any rate. **Hash-based exhaustion.**Both exhaustion arguments use 64-bit hashing to recognise a repeated state, so both hold modulo collisions. The probabilities are about 3 × 10-8 for Proposition 2 and 2 × 10-4 for the instance in Section 9.
Conclusion
The move search in the challenge repository, with total length rising before it falls.
The same weight then bounds what the search can reach, because the priority is at least w times the depth. That is the first of three limits this paper measures rather than argues. The second is on precomputation: the backward half of a bidirectional search never reads the presentation, so it can be built once and shared, and one such set of 22,000,000 states contained 2 of the 10,115 presentations, because the bound that makes it reach deep is the bound that makes it narrow. The third is economic and it is the paper’s structural result. Under a tie rule that halves a record’s value for each further holder, competence and point value are anti-correlated by construction, since a record is widely shared precisely when it is easy to reach. Measured: 146 held records paid 3.16 points, while 1,012 records the same search could not reach were worth about 388, and five architectures returned nothing on that band.
What remains open has a shape. Every method measured here is competent exactly where the optimum is short, and the presentations with long records are the ones where no method reached any reduction at all. A learned policy is the relevant class of method, and the cheapest stand-in for one, a least-squares estimate of distance, halved the error of total relator length and moved the competence boundary outward without converting a single reach into a score. Two smaller openings are worth naming because they are concrete. An admissible invariant strong enough to prune at depth 20 would turn the conditional non-existence statement of Section 9 into a theorem, and the only admissible invariant available has a median value of 5. And the exhaustion argument that proves reductions must go uphill stops working at slack 12, which is exactly where knowing how far uphill they must go would begin to be interesting. Section 13 lists the run outputs behind every table, so each of these figures can be recomputed rather than taken on trust.
Data and code availability
All code, data and run logs live at
https://github.com/Amey-Thakur/SAIR-ANDREWS-CURTIS-CHALLENGE
[13]. The priority search is runs/pool/bestfirst.py, the
bounded bidirectional search is runs/pool/jit_tieband.py, the shared
backward set is runs/pool/ball_search.py, the fitted estimate and the
searches that use it are runs/pool/learn_heuristic.py,
runs/pool/astar.py and runs/pool/idastar.py, and the
exponent-sum bound is runs/pool/matdist.py. The run outputs behind
every table are in runs/pool/, one file per run, and
runs/campaign_log.md records each measurement as it was taken,
including the three that were later corrected. The move specification, the
presentations and the reference verifier are the competition’s own
[9].
Table 1 is dw1.out, dw4.out,
dw12.out and bfcheck.out; Proposition 2 is
uns0.out, uns4.out, unsw12.out and
unsw20.out; Table 3 is ballcheck.out and
bulk.out; Table 7 is DEC2.out. The length
profile in Figure 1 is computed from the verified reduction
stored in runs/pool/tieband6/solutions.jsonl. Reproducing the
measurements needs Python 3.10 or later, NumPy and numba; the verifier needs the
standard library alone.
Citation
Please cite this work as:
Thakur, Amey. "Length as Priority, Not Constraint: Search Geometry of the Andrews-Curtis Challenge Pool" (Nov 2026). https://github.com/Amey-Thakur/SAIR-ANDREWS-CURTIS-CHALLENGE.Or use the BibTex citation:
@article{thakur2026andrewscurtis,
title = "Length as Priority, Not Constraint: Search Geometry of the Andrews-Curtis Challenge Pool",
author = "Thakur, Amey",
year = "2026",
month = "Nov",
url = "https://github.com/Amey-Thakur/SAIR-ANDREWS-CURTIS-CHALLENGE"
}