PaperlayerView exact revision on arXiv

Source-linked AI summary

PatternBoost: Constructions in Mathematics with a Little Help from AI

François Charton, Jordan S. Ellenberg, Adam Zsolt Wagner, Geordie Williamson

arXiv:2411.00566v1math.COcs.LG

TL;DR

The paper addresses how to discover interesting mathematical constructions, especially when useful patterns are difficult to understand explicitly. PatternBoost alternates local search with transformer-based global sampling, and its performance is often impressive across extremal-combinatorics problems, though it varies by problem and can fail to improve on difficult instances.

  • Problem

    The paper seeks a general method for discovering or approaching mathematical constructions whose underlying patterns may be difficult to understand explicitly.

    Source: §1 · pp. 1–2

  • Method

    PatternBoost alternates local search that improves constructions with a transformer trained on strong examples to generate seeds for further search.

    Source: §1 · p. 1, Step 2: Training the transformer · p. 6, §6 · p. 25

  • Results

    PatternBoost often improves local-search results, including a triangle-free graph with 48 edges from global search alone versus about 66 edges typically reached by the alternating method.

    Source: §1 · p. 2, Discussion · p. 7

  • Takeaways & Limitations

    PatternBoost provides an accessible, broadly applicable tool for mathematical construction problems, particularly when good constructions exhibit complicated patterns.

    Source: §1 · p. 2, §6 · p. 25

    Performance varies across problems, and one difficult box-covering instance remained at 82 boxes despite PatternBoost and Gurobi, suggesting that a smarter local search method was needed.

    Source: §3.1.2 · p. 10, §4.5 · p. 23

Abstract

from arXiv · show

We introduce PatternBoost, a flexible method for finding interesting constructions in mathematics. Our algorithm alternates between two phases. In the first ``local'' phase, a classical search algorithm is used to produce many desirable constructions. In the second ``global'' phase, a transformer neural network is trained on the best such constructions. Samples from the trained transformer are then used as seeds for the first phase, and the process is repeated. We give a detailed introduction to this technique, and discuss the results of its application to several problems in extremal combinatorics. The performance of PatternBoost varies across different problems, but there are many situations where its performance is quite impressive. Using our technique, we find the best known solutions to several long-standing problems, including the construction of a counterexample to a conjecture that had remained open for 30 years.

1 Introduction

PatternBoost alternates local search with transformer-based global sampling to generate mathematical constructions, aiming to make pattern discovery more accessible and broadly applicable. The paper positions this approach within neural optimization and transformer research while emphasizing its potential beyond extremal combinatorics.

1 Introduction

  • PatternBoost alternates a typically greedy local search with a transformer-based global step that proposes better starting points.The method is presented as an additional layer over local search, with the transformer trained to suggest promising constructions.Source: §1 · pp. 1–2
  • Its motivation is to help automate the difficult human process of recognizing patterns among mathematical objects and generating new examples of the same kind.The authors hope transformers can abstract features from presented mathematical entities and produce further related examples.Source: §1 · pp. 1–2
  • PatternBoost is intended as an accessible tool for mathematicians, often using transformers off the shelf without extensive machine-learning expertise or industry-level computing resources.The authors note that choices such as tokenization can still affect performance.Source: §1 · p. 2
  • The paper applies the method mainly to extremal combinatorics but argues that its underlying procedure is not specific to mathematics.The authors identify mechanically quick and reliable evaluation as crucial in mathematics and potentially more difficult in other domains.Source: §1 · p. 2

Related works

  • Related work includes neural optimization, transformer architectures, and neural methods applied to mathematical research problems such as combinatorics, graph conjectures, and control theory.The paper connects PatternBoost to prior uses of neural networks for optimization and research-level mathematical tasks.Source: Related works · pp. 2–3

2 A simple illustrative problem: many edges with no triangles

PatternBoost alternates simple local search with transformer-based global search to discover high-scoring triangle-free graphs. In this example, transformer-generated seeds substantially improve local-search outcomes and converge toward complete bipartite graphs.

2 A simple illustrative problem: many edges with no triangles

  • PatternBoost targets the extremal problem of maximizing edges in an n=20 graph without triangles, using a score function to rank candidate constructions.The motivating structure is bipartite, which achieves the optimum in this example.Source: §2 · pp. 3–4
  • Local search repeatedly deletes edges from triangles, then adds random edges without creating triangles, while never decreasing the score.The paper deliberately uses this simple two-phase protocol to illustrate local-global iteration.Source: §2 · p. 4

Step 1: Create a starter database

  • From 40,000 empty-graph searches, the best score was 99 versus the optimum 100, while the distribution peaked at 66; the top 25% formed the transformer’s training set.The starter database was generated by repeatedly running local search from the empty graph.Source: Step 1: Create a starter database · p. 5, Figure 1 · p. 5

Step 2: Training the transformer

Step 3: Obtain new constructions from the transformer

  • Only 37,000 of 100,000 generated sequences had the correct 190 entries for valid 20-vertex adjacency matrices, limiting which samples could be scored.The paper suggests model size, training-set size, or training duration as possible reasons for invalid outputs.Source: Step 3: Obtain new constructions from… · p. 6

Step 4: Run local search from the new constructions obtained from the transformer

  • 46 score-100 graphs and 47 score-99 graphs emerged from 37,000 transformer-generated seeds, versus only two score-99 graphs previously.The score distribution shifted after one iteration, and all resulting graphs were distinct but isomorphic to the unique extremal graph.Source: Step 4: Run local search from the new… · p. 7, Figure 3 · p. 7

Step 5: Repeat this process

  • Repeating the process for five more generations makes the model produce essentially only complete bipartite graphs, mostly with equal part sizes.Larger transformers and training sets are needed for more intricate patterns to provide sufficient context and avoid overfitting or coincidental false leads.Source: Step 5: Repeat this process · p. 7, Discussion · p. 7

Discussion

  • Global search alone performs poorly, finding only a 48-edge triangle-free graph after fifty loops, whereas local-global alternation outperforms local search alone.Local search alone most often reaches triangle-free graphs with about 66 edges.Source: Discussion · pp. 7–8

3 Hard and easy problems

PatternBoost alternates local search with transformer-guided global sampling, with performance varying substantially across extremal-combinatorics problems. It reaches strong no-squares results, nearly matches a specialized permanent search, and refutes a 30-year-old hypercube conjecture.

3 Hard and easy problems

  • PatternBoost’s performance varies by problem: it improves local search, nearly matches specialized human-designed search, and can refute long-standing conjectures.The three examples respectively show weaker competitiveness, near-parity with tailored methods, and a counterexample.Source: §3 · p. 8

3.1 The no-squares problem

  • The no-squares problem is difficult for machine learning methods, while the 312-avoiding permanent problem and hypercube problem provide stronger successes.The no-squares problem’s exact optimum is known through n = 40, whereas the other examples show near-specialized performance and a conjecture counterexample.Source: §3.1 · p. 8, §3.2 · p. 11, §3.3 · p. 14

3.1.2 The advantage of larger models, and better tokenizers

  • 96 edges were found for the n = 33 no-squares problem after 116.5 million local searches, matching the maximum possible score.The result used a 6-layer, 128-dimensional transformer with 4 attention heads and the improved tokenizer.Source: §3.1.2 · p. 10
  • PatternBoost found 91-edge graphs versus 89-edge graphs for local search alone, and 2750 graphs with at least 89 edges versus 5.These distributions were compared after 50 million local-search steps.Source: §3.1.2 · p. 10, Table 2 · p. 10

3.1.3 Scaling PatternBoost

  • The no-squares experiments scale to n ≤ 30 within 80 million local searches, while the best n = 33 solution required 116.5 million.Models were trained for sizes from n = 20 through n = 55.Source: §3.1.3 · p. 11

3.2 The 312-avoiding permanent problem

  • For the 312-avoiding permanent problem, PatternBoost reached 5,101,230, close to the human method’s 5,200,384 despite being generic.The specialized human method still achieved the higher score after a two-week comparison.Source: §3.2 · pp. 12–13

3.2.1 Combining methods

  • Adding 1000 human-method constructions produced 41 new PatternBoost constructions with permanents between 5.1·10^6 and 5.2·10^6, though none exceeded the Figure 8 high score.The new constructions were unseen by either method before.Source: §3.2.1 · pp. 13–14

3.3 Spanning subgraphs of the d-cube with diameter d

  • A spanning subgraph of the 6-cube with diameter 6 and 81 edges disproves Graham ’s conjectured optimum of 82 edges and marks the first progress on this problem in 30 years.Source: §3.3 · pp. 14–15, Figure 10 · p. 15

4 Other problems

PatternBoost was applied to five extremal-combinatorics problems, producing stronger constructions in several settings while revealing problem-dependent computational and modeling limits.

4.1 No isosceles triangles

  • For n up to approximately 32, SAT solvers found and proved optimal constructions, although some parameter values had multiple structurally different optima.The computed values appeared linear in n, but the underlying pattern was difficult to describe or generalize manually.Source: §4.1 · pp. 16–17, Figure 11 · p. 16, Figure 12 · p. 16
  • 110 points were found in [64]^2 without an isosceles triangle, improving the 108-point standard-search construction; at n = 100, PatternBoost improved 154 points to 160.The authors found many 110-point constructions but none better, while the likely optimum near n = 100 was around 176 points.Source: §4.1 · p. 17, Figure 14 · p. 18, Figure 15 · p. 18

4.2 The “no 5 on a sphere” problem

  • The no-5-on-a-sphere problem is difficult because constraint checks involve enormous numbers of point tuples and 5 × 5 determinants, making naive searches prohibitively slow.GPU determinant evaluation and cube-symmetry augmentation enabled PatternBoost runs for grid sizes through n = 10.Source: §4.2 · pp. 18–19

4.3 Saturated Sperner systems of small size

  • PatternBoost constructed a saturated 8-Sperner system of size 108, improving the bound to ϵ = 0.04085, although the problem lacked an obvious reward function.The score was ad hoc and further improvements may follow from better structural understanding.Source: §4.3 · p. 21, Figure 18 · p. 21

4.4 Cross-Sperner systems

  • For several small (n, k) pairs, PatternBoost beat earlier cross-Sperner constructions, but it did not exceed the conjectured upper bound.Table 4 compares the constructions with the conjectured bounds.Source: §4.4 · pp. 21–22, Table 4 · p. 22

4.5 Double covers of high dimensional boxes

  • The authors found double covers of {0, 1, 2}^d using approximately 1.28 · 2^d proper sub-boxes, but neither PatternBoost nor Gurobi reached fewer than 82 boxes for d = 6.They suggest that a smarter local-search method is needed for further progress.Source: §4.5 · p. 23, Table 5 · p. 23

5 Machine learning settings

The paper represents mathematical constructions as token sequences, trains decoder-only transformers to predict next tokens, and samples complete candidate solutions for downstream search.

Model

  • The decoder-only transformer predicts each next token from the preceding prefix, using token and positional embeddings followed by self-attention and feed-forward layers.The model outputs next-token probabilities after decoding the final transformer representations.Source: §5 · pp. 23–24

Training

  • Training minimizes cross-entropy over the actual sequence tokens, with parameters updated by AdamW while monitoring training and external test loss to avoid overfitting.The reported settings use batches of 32, learning rate 5 · 10^-4, weight decay 0.01, and 2–6 transformer layers.Source: §5 · p. 24

Generation

  • After training, the model autoregressively samples tokens from an empty sequence until a full candidate construction is generated.These generated sequences are intended to resemble promising solutions in the training data and can seed local search.Source: §5 · p. 24

Tokenization

  • Mathematical constructs are tokenized into sequences because naive binary encodings create long inputs whose transformer attention cost scales quadratically with sequence length.The paper shortens sequences by grouping binary entries or learning frequent subsequences with byte pair encoding.Source: §5 · pp. 24–25

6 Concluding remarks

PatternBoost is presented as a versatile method for discovering mathematical constructions through local search and global transformer learning. Its usefulness depends on recognizing patterns in good constructions and tailoring local search to each problem.

6 Concluding remarks

  • PatternBoost combines local improvement with a global transformer trained on strong constructions to generate new starting points.The local search makes small modifications, while the global model learns from the best constructions.Source: §6 · p. 25
  • The method appears most useful when good constructions follow patterns that are difficult for humans to understand fully.Source: §6 · p. 25
  • Even with the simplest local search, PatternBoost achieved state-of-the-art results in multiple cases.The authors recommend tailoring local search to the target problem because this can significantly improve performance.Source: §6 · p. 25
  • PatternBoost is designed to be accessible to mathematicians without deep machine-learning expertise and adaptable across mathematical applications.Source: §6 · p. 25
  • The authors anticipate that problem-specific local-search adaptations will expand automated mathematical construction and collaboration between mathematics and artificial intelligence.Source: §6 · p. 25

A A proof of a lower bound on sets without isosceles triangles

The proof obtains a lower bound for sets in the n×n grid without isosceles triangles by randomly sampling points and deleting triangle peaks. Choosing p = ϵ n√log n yields a set of size at least ϵ′ n√log n.

A A proof of a lower bound on sets without isosceles triangles

C A saturated 8-Sperner system of size 108

This construction describes a saturated 8-Sperner system through two families of sets. The listed families contain 108 sets in total.

C A saturated 8-Sperner system of size 108

E A double cover of {0, 1, 2}5 with 41 boxes

The construction lists boxes B1 through B41 as products of subsets of {0, 1, 2}. These displayed products specify the component choices used in the construction.

E A double cover of {0, 1, 2}5 with 41 boxes

F A spanning subgraph of the 6-cube with 81 edges and diameter 6

The passage introduces a listing of the subgraph’s edges.

Loading 2411.00566v1…