Heilbronn's triangle problem
Heilbronn's triangle problem in the unit square: configurations of 11 to 16 points, every one checked in exact arithmetic

| 1 | --- |
| 2 | issue: 2 |
| 3 | status: working |
| 4 | --- |
| 5 | # Reproduction of Comellas and Yebra's 12-point configuration |
| 6 | |
| 7 | This route reproduces the published construction to the project's ten decimal |
| 8 | places. It is not a new record or a proof of optimality. |
| 9 | |
| 10 | ## Source and construction |
| 11 | |
| 12 | F. Comellas and J. L. A. Yebra, *New lower bounds for Heilbronn numbers*, |
| 13 | Electronic Journal of Combinatorics 9 (2002), R6, page 7, "Twelve points": |
| 14 | [article](https://doi.org/10.37236/1623), |
| 15 | [PDF](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v9i1r6/pdf/). |
| 16 | Accessed 2026-11-12; the formula and coordinate table were also checked visually |
| 17 | on the original PDF page. |
| 18 | |
| 19 | Write t = (27 + 3 sqrt(57))^(1/3), x = 1 - (t^2 + 6)/(6t), |
| 20 | and y = 2x^2 - 3x + 1/2. The 12 points are, in the paper's order: |
| 21 | (x,0), (1-x,0), (0,x), (1,x), (1/2,y), (y,1/2), (1-y,1/2), |
| 22 | (1/2,1-y), (0,1-x), (1,1-x), (x,1), (1-x,1). |
| 23 | |
| 24 | `generate.py` uses Python's standard-library Decimal with 100 significant digits |
| 25 | for its default output, Newton iteration for the positive cube root, and 60 |
| 26 | digits after the decimal point for each coordinate. It never uses binary floats |
| 27 | to calculate coordinates. This is deterministic evaluation of the published |
| 28 | formula, not a search; a seed does not apply. |
| 29 | |
| 30 | ## Reproduce and check |
| 31 | |
| 32 | From the repository root, with Python 3 and no extra dependencies: |
| 33 | |
| 34 | ```sh |
| 35 | python3 routes/codex/n12-reproduction/generate.py > routes/codex/n12-reproduction/n12.txt |
| 36 | python3 verify.py routes/codex/n12-reproduction/ |
| 37 | ``` |
| 38 | |
| 39 | Local run on 2026-11-12, Python 3.9.6: generation took less than 0.001 seconds. |
| 40 | The unchanged project verifier enumerated all 220 triangles with exact rational |
| 41 | arithmetic and printed: |
| 42 | |
| 43 | ```text |
| 44 | n12.txt: 12 points in the unit square, smallest triangle 0.0325988586, on lines 1, 5 and 7 |
| 45 | n = 12: 0.0325988586 |
| 46 | ``` |
| 47 | |
| 48 | `n12.txt` SHA-256: |
| 49 | `fec1694bab8c1864318ae2f83928aca6b871b94a7b03721202a59e32945f2a43`. |
| 50 | Regenerating the file reproduced its bytes exactly. The submitted decimal points |
| 51 | are rational approximations to irrational coordinates; the exact check is of |
| 52 | these submitted rationals. Matching ten displayed decimals does not assert exact |
| 53 | equality with the algebraic construction's area. |
| 54 | |
| 55 | ## Precision experiment and limitations |
| 56 | |
| 57 | The same generator, changing only `--digits`, gave these exact-check displays: |
| 58 | |
| 59 | | Decimal places | Smallest triangle, cut to ten decimals | |
| 60 | | --- | --- | |
| 61 | | 6 | 0.0325987100 | |
| 62 | | 10 | 0.0325988586 | |
| 63 | | 30 | 0.0325988586 | |
| 64 | | 60 (submitted) | 0.0325988586 | |
| 65 | |
| 66 | Six-decimal output is valid but misses the reproduction target. Ten decimals |
| 67 | already match its displayed value in this run; 60 are retained to preserve a much |
| 68 | closer approximation. Rounding also changes which near-tied triangle is smallest. |
| 69 | The logs and generation timings are in `reproduction.json`. Only `n12.txt` is |
| 70 | submitted as the route's configuration; the lower-precision files were temporary. |
| 71 | |
| 72 | ## Next |
| 73 | |
| 74 | Read the remote verify status on the commit holding these coordinates. If it |
| 75 | reports n = 12: 0.0325988586, submit this reproduction for maintainer review; the |
| 76 | maintainer can then use the verified route as evidence for the n = 12 entry in |
| 77 | KNOWN.md. Improving the published value would be a separate search, not a result |
| 78 | of this reproduction. |