Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 23 min ago
PreprintCC BY 4.0arXiv

A (log n)1/4 Bound for the Komlós Problem

  • Eren Ercan
Open at sourcePDFDOICite

Abstract

Let A∈ℝm× n have columns of Euclidean norm at most one. We prove that disc(A)≤2395(1+log+n/9)1/4+2√2. Here log+t=max{0,log t}. Building on Bansal and Jiang's affine spectral independence framework, we remove the (loglog n)7/4 factor from their bound. The fourth root comes from balancing the logarithmic decrease in the alive dimension against the fourth power of the row thresholds. Historical exponential sums control the covariance budget across size classes with summable thresholds. An exact threshold-sum certificate gives the coefficient $2395$, and rounding at most eight remaining fractional coordinates costs 2√2. The finite construction also gives partial colourings from any prescribed starting point and at any prescribed depth, preserving existing signs. We formalize the partial- and full-colouring theorems in Lean, including the finite trajectory, exact threshold sum and final rounding, with Bansal--Jiang Theorem A.4 as the sole external research theorem assumption.

Related

  1. An Exposition of the Õ(log1/4 n) Bound for the Komlós Problem
    Nikhil Bansal, Haotian Jiang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  2. An explicit lower bound for the unit distance problem
    Will Sawin
    arXiv (Cornell University)PreprintLicence not statedFull text30 citedCombinatorics & discrete mathematicsOpenAlex
  3. A Uniform Bound on Optimal Strategy Length in Water Transport Problem
    Tianyi Tao, Bohan Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A near-quadratic lower bound for the Brown--Erdős--Sós (9,6)-problem
    Xiangliang Kong, Chong Shangguan, Xin Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. A new lower bound for the Schur-Siegel-Smyth trace problem
    David Niedbala Giraudin
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{ercan2026bound,
  title = {{A $(\log n)^1/4$ Bound for the Komlós Problem}},
  author = {Eren Ercan},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.08885},
  eprint = {2609.08885},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.08885},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A (log n)^1/4 Bound for the Komlós Problem
AU  - Eren Ercan
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.08885
UR  - https://arxiv.org/abs/2609.08885
AB  - Let A∈ℝ^m× n have columns of Euclidean norm at most one. We prove that disc(A)≤2395(1+log_+n/9)^1/4+2√2. Here log_+t=max{0,log t}. Building on Bansal and Jiang's affine spectral independence framework, we remove the (loglog n)^7/4 factor from their bound. The fourth root comes from balancing the logarithmic decrease in the alive dimension against the fourth power of the row thresholds. Historical exponential sums control the covariance budget across size classes with summable thresholds. An exact threshold-sum certificate gives the coefficient $2395$, and rounding at most eight remaining fractional coordinates costs 2√2. The finite construction also gives partial colourings from any prescribed starting point and at any prescribed depth, preserving existing signs. We formalize the partial- and full-colouring theorems in Lean, including the finite trajectory, exact threshold sum and final rounding, with Bansal--Jiang Theorem A.4 as the sole external research theorem assumption.
ER  -