Fourier analysis, linear programming, and densities of distance avoiding sets in R^n

In this paper we derive new upper bounds for the densities of measurable sets in R^n which avoid a finite set of prescribed distances. The new bounds come from the solution of a linear programming problem. We apply this method to obtain new upper bounds for measurable sets which avoid the unit distance in dimensions 2,..., 24. This gives new lower bounds for the measurable chromatic number in dimensions 3,..., 24. We apply it to get a new, short proof of a recent result of Bukh which in turn generalizes theorems of Furstenberg, Katznelson, Weiss and Bourgain and Falconer about sets avoiding many distances.

• Publication year

  2008

• Venue

  EURASIP Journal on Advances in Signal Processing

• Publication date

  2008-08-13

• Fields of study

  Mathematics

• Identifiers
  DOI 10.4171/JEMS/236arXiv 0808.1822
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Lower Bounds for Measurable Chromatic Numbers

  2008cited by this paper
• Measurable Sets With Excluded Distances

  2007influential reference
• New upper bounds on sphere packings I

  2001cited by this paper
• Special Functions

  1996influential reference
• Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability

  1995influential reference
• Unsolved Problems In Geometry

  1991cited by this paper
• Ergodic Theory and Configurations in Sets of Positive Density

  1990cited by this paper
• Bounds on the measurable chromatic number of Rn

  1989cited by this paper
• Plane Sets with Positive Density at Infinity Contain all Large Distances

  1986cited by this paper
• A szemerédi type theorem for sets of positive density inRk

  1986cited by this paper
• The Realization of small Distances in Plane Sets of Positive Measure

  1986influential reference
• Measurable chromatic number of geometric graphs and sets without some distances in euclidean space

  1984cited by this paper
• The Realization of Distances in Measurable Subsets Covering Rn

  1981influential reference
• A Treatise on the Theory of Bessel Functions

  1945cited by this paper
• Metric spaces and completely monotone functions

  1938cited by this paper
• Bessel Functions. (Scientific Books: A Treatise on the Theory of Bessel Functions)

  1923cited by this paper
• A SZEMERI DI TYPE THEOREM FOR SETS OF POSITIVE DENSITY IN R k

  year unknowncited by this paper

• Conic optimization for extremal geometry

  2025cites this paper
• Obtuse almost-equiangular sets

  2025cites this paper
• Clustering in typical unit-distance avoiding sets

  2024cites this paper
• Spherical sets avoiding orthonormal bases

  2023cites this paper
• Optimization hierarchies for distance-avoiding sets in compact spaces

  2023cites this paper
• Prime and polynomial distances in colourings of the plane

  2023cites this paper
• A linear programming approach to Fuglede’s conjecture in Zp3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {Z

  2023cites this paper
• A linear programming approach to Fuglede's conjecture in $\mathbb{Z}_p^3$

  2022cites this paper
• Odd Distances in Colourings of the Plane

  2022cites this paper
• The density of planar sets avoiding unit distances

  2022cites this paper
• A recursive Lovász theta number for simplex-avoiding sets

  2021cites this paper
• Geometrical sets with forbidden configurations

  2021cites this paper
• Density Estimates of 1-Avoiding Sets via Higher Order Correlations

  2020influential citation
• Density Estimates of 1-Avoiding Sets via Higher Order Correlations

  2020influential citation
• Lower Bounds for the Measurable Chromatic Number of the Hyperbolic Plane

  2018cites this paper
• Complete positivity and distance-avoiding sets

  2018cites this paper
• On the density of planar sets without unit distances

  2018cites this paper
• On a generalization of the Hadwiger–Nelson problem

  2017influential citation
• Polynomial configurations in sets of positive upper density over local fields

  2017cites this paper
• Preface Issue 4-2014

  2017cites this paper
• Lower Bounds for the Measurable Chromatic Number of the Hyperbolic Plane

  2017cites this paper
• A Fourier analízis válogatott alkalmazásai

  2016influential citation
• On a generalization of the Hadwiger–Nelson problem

  2015cites this paper
• The fractional chromatic number of the plane

  2015cites this paper
• Distance-Avoiding Sets in the Plane

  2015cites this paper
• PhD subject: infinite graphs and mathematical programming

  2015cites this paper
• Some old and new problems in combinatorial geometry I: around Borsuk's problem

  2015cites this paper
• On some problems of Euclidean Ramsey theory

  2015cites this paper
• New lower bound for the chromatic number of a rational space with one and two forbidden distances

  2015cites this paper
• New lower bound for the chromatic number of a rational space with one and two forbidden distances

  2015cites this paper
• On the measurable chromatic number of a space of dimension n ≤ 24

  2015cites this paper
• The Density of Sets Avoiding Distance 1 in Euclidean Space

  2015influential citation
• Better Bounds for Planar Sets Avoiding Unit Distances

  2015influential citation
• On some problems of Euclidean Ramsey theory

  2015influential citation
• Quantum information, Bell inequalities and the no-signalling principle

  2014cites this paper
• Alexander Soifer: “The Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of Its Creators”

  2014cites this paper
• Spectral bounds for the independence ratio and the chromatic number of an operator

  2014cites this paper
• Alexander Soifer: “The Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of Its Creators”

  2014cites this paper
• An Improvement on the Delsarte-Type LP-Bound with Application to MUBs

  2014cites this paper
• The Density of Sets Avoiding Distance 1 in Euclidean Space

  2014cites this paper
• Better Bounds for Planar Sets Avoiding Unit Distances

  2014cites this paper
• Coloring Distance Graphs and Graphs of Diameters

  2013cites this paper
• Semidefinite programming in combinatorial optimization with applications to coding theory and geometry

  2013influential citation
• Open Sets Avoiding Integral Distances

  2013cites this paper
• Spectral bounds for the independence ratio and the chromatic number of an operator

  2013cites this paper
• Squares and Difference Sets in Finite Fields

  2013cites this paper
• Bloch-sphere colorings and Bell inequalities

  2013cites this paper
• Open Sets Avoiding Integral Distances

  2012cites this paper
• A quantitative version of Steinhaus’ theorem for compact, connected, rank-one symmetric spaces

  2012influential citation
• Invariant Semidefinite Programs

  2010cites this paper
• A quantitative version of Steinhaus’ theorem for compact, connected, rank-one symmetric spaces

  2010influential citation
• Topics in exact precision mathematical programming

  2010cites this paper
• A ug 2 00 8 LOWER BOUNDS FOR MEASURABLE CHROMATIC NUMBERS

  2009cites this paper
• New Bounds for Geometric Packing and Coloring via Harmonic Analysis and Optimization

  2009cites this paper
• Lecture notes: Semidefinite programs and harmonic analysis

  2008cites this paper
• Lower Bounds for Measurable Chromatic Numbers

  2008influential citation
• Comptes Rendus Mathématique

  year unknowncites this paper
• Konrad-zuse-zentrum F ¨ Ur Informationstechnik Berlin Improving the Accuracy of Linear Programming Solvers with Iterative Refinement Improving the Accuracy of Linear Programming Solvers with Iterative Refinement *

  year unknowncites this paper