{"id":"palomar/PALOMAR-2026-09-06-000005","url":"https://github.com/gdahia/DensityHalesJewett/tree/1285e649d0256a848d4693377dd1244065ac49ff","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-09-06-000005-v1.json","repo":"https://github.com/gdahia/DensityHalesJewett","tags":["math.CO","msc:05D10","msc:05A05","msc:11B75","msc:68R15","extremal-combinatorics","lean-formalization","arithmetic-progressions"],"score":0,"title":"The density Hales–Jewett theorem and Szemerédi's theorem","trust":"high","domain":"math.CO","source":"palomar","authors":["Gabriel Dahia"],"reviews":0,"subject":"math.CO","summary":"A Lean 4 formalization of the density Hales–Jewett theorem: for every finite alphabet α and every density δ > 0, all sufficiently large n have the property that any set of at least δ·|α|^n words of length n over α contains a combinatorial line. The basis for the formalization is the combinatorial proof of Dodos, Kanellopoulos, and Tyros. As a consequence, we also formalize Szemerédi's theorem on the integers: for every k ≥ 3 and δ > 0, the following holds for all sufficiently large n. Any subset of {0, …, n−1} of size at least δ·n contains a nonconstant arithmetic progression of length k.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-09-06","reactions":{},"formalized":true,"formalizes":[{"title":"A Simple Proof of the Density Hales--Jewett Theorem","identifier":"https://doi.org/10.1093/imrn/rnt041","relationship":"formalizes"}]}