Density Estimates of 1-Avoiding Sets via Higher Order Correlations
- PDF / 339,954 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 181 Views
Density Estimates of 1-Avoiding Sets via Higher Order Correlations Gergely Ambrus1
· Máté Matolcsi1,2
Received: 23 June 2020 / Revised: 20 October 2020 / Accepted: 1 November 2020 © The Author(s) 2020
Abstract We improve the best known upper bound on the density of a planar measurable set A containing no two points at unit distance to 0.25442. We use a combination of Fourier analytic and linear programming methods to obtain the result. The estimate is achieved by means of obtaining new linear constraints on the autocorrelation function of A utilizing triple-order correlations in A, a concept that has not been previously studied. Keywords Chromatic number of the plane · Distance-avoiding sets · Linear programming · Harmonic analysis Mathematics Subject Classification 42B05 · 52C10 · 52C17 · 90C05
1 Introduction What is the maximal upper density of a measurable planar set A with no two points at distance 1? This 40-year-old question has attracted some attention recently, with a sequence of progressively improving estimates, the strongest of which currently being that of Bellitto et al. [3], who gave the upper estimate 0.25646. In the present article, we
Editor in Charge: János Pach G. Ambrus was supported by the NKFIH Grant No. PD125502 and the Bolyai Research Fellowship of the Hungarian Academy of Sciences. M. Matolcsi was supported by the NKFIH Grant Nos. K132097 and K129335. Gergely Ambrus [email protected] Máté Matolcsi [email protected] 1
Alfréd Rényi Institute of Mathematics, POB 127, Budapest 1364, Hungary
2
Budapest University of Technology and Economics (BME), Egry J. u. 1, Budapest 1111, Hungary
123
Discrete & Computational Geometry
provide the new upper bound of 0.25442, getting enticingly close to the upper estimate of 0.25 conjectured by Erd˝os. Our argument builds on the Fourier analytic method of [8]. The main new ingredient is to estimate certain triple-order correlations in A which lead to new linear constraints for the autocorrelation function f corresponding to A. Let A be a Lebesgue measurable, 1-avoiding set in R2 , that is, a measurable subset of the plane containing no two points at distance 1. Denote by m 1 (R2 ) the supremum of possible upper densities of such sets A (for the rigorous definition, see Sect. 2). Erd˝os conjectured in [6] that m 1 (R2 ) is less than 1/4, a conjecture that has been open ever since. One of the easiest upper bounds for m 1 (R2 ) is 1/3, shown by the fact that A may contain at most one of the vertices of any regular triangle of edge length 1. This simple idea was strengthened by Moser [9] using a special unit distance graph, the Moser spindle, implying that m 1 (R2 ) ≤ 2/7 ≈ 0.285. Székely [11] improved the upper bound to ≈ 0.279. Applying Fourier analysis and linear programming Oliveira Filho and Vallentin [10] proved that m 1 (R2 ) ≤ 0.268, which was further improved to ≈ 0.259 by Keleti et al. [8]. Recently, Bellitto et al. [3] (see also Bellitto [2]) used a purely combinatorial argument—based on the fractional chromatic number of finite graphs—to reach
Data Loading...
