Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Distance Problems

aggarwal_2015_unit_distances_convex_polygon/: Improves the upper bound for unit distances among the vertices of a convex n-gon to n log_2 n + 4n and answers a question of Fishburn and Reeds negatively.

alexeev_2024_erdos_unit_distance_problem_small_point/: Computes the maximum number of unit distances among n planar points exactly for n up to 21 and improves upper bounds to 30.

altman_1963_problem_p_erdos/: Altman's 1963 proof of Erdős's conjecture that the vertices of a plane convex n-gon determine at least [n/2] distinct distances, sharp for the regular polygon, with a companion theorem that a convex (2N+1)-gon with exactly N distinct distances is regular; a planar paper that prints no statement about polyhedra or three dimensions.

anning_1945_integral_distances/: Proves no infinite non-collinear plane set has all pairwise distances integral, while n such points exist for every n.

apfelbaum_2010_improved_bound_number_unit_area_triangles/: Proves that n points in the plane span at most O(n^(9/4+eps)) triangles of unit area, improving the previous O(n^(44/19)) bound.

aronov_2004_distinct_distances_three_higher_dimensions/: Shows n points in three dimensions determine at least about n^(77/141), roughly n^0.546, distinct distances, beating the earlier n^(1/2) bound.

ascher_2019_erdos_ulam_problem_lang_s_conjecture/: Assuming Lang's conjecture, the sizes of rational distance sets in general position in the plane are bounded by one universal constant.

avis_1988_repeated_distances_space/: Bounds the number of edges of repeated-distance graphs in d dimensions, with near-matching bounds for the furthest-neighbor graph in three dimensions.

barany_2013_question_famous_paper_erdos/: Bárány and Roldán-Pensado's study of Erdős's 1946 statement that every convex curve has a point whose centred circles meet it at most twice: with N(K) the least such bound over boundary points, they construct a convex 15-gon with N(K) = 6, prove N(K) finite for every planar convex body, build for each ε > 0 a body on which centres of circles meeting the boundary infinitely often fill more than a (1 − ε)-fraction of the perimeter, and show that for most bodies, in the Baire category sense, most boundary points are centres of circles meeting the boundary in at least n points for every n.

bezdek_2013_contact_graphs_unit_sphere_packings_revisited/: Improves the upper bound on touching pairs in a packing of n unit balls in 3-space and bounds touching triplets and quadruples.

bezdek_2018_contact_numbers_sphere_packings/: Surveys maximum contact numbers of finite sphere packings, equivalent to the largest number of repeated shortest distances among n points.

bhowmick_2024_problem_erdos_about_rich_distances/: Constructs n-point planar sets in which about n/4 distances each occur more than n times, answering an old Erdos question.

blokhuis_1984_few_distance_sets/: Bounds sets with few distances and proves an isosceles set in d-space has at most half of d plus one times d plus two points.

burt_2015_crescent_configurations/: Shows that for every n at least 3 there are n points in general position in (n-2)-dimensional space whose n-1 distinct distances occur with multiplicities 1 through n-1, and records a lattice search that found no nine-point planar example.

cantwell_1996_finite_euclidean_ramsey_theory/: Shows every two-coloring of four-dimensional space contains a monochromatic square, and improves chromatic number bounds in dimensions four and five.

charalambides_2013_note_distinct_distance_subsets/: Shows any N points in the plane or on the two-dimensional sphere contain a subset of size at least a constant times N^(1/3)/log N with all pairwise distances distinct.

chen_2025_bounds_two_distance_sets_euclidean_space_unit_sphere/: Records the Euclidean ratio-bound lead in Chen and Yu's paper, including the missing denominator hypothesis and the valid undivided inequality.

chojecki_2026_erdos_problem_655_natural_repairs_exact/: Shows the regular n-gon is exactly extremal under the local circle condition of Erdős problem 655, so the site's wording, and every repair that still admits the regular n-gon, is false.

chojecki_2026_order_growth_planar_sets_avoiding_integer/: Proves that a measurable planar set in a disk of radius R avoiding integer distances has measure at most order square root of R, which with Sárközy's lower bound gives the growth exponent 1/2.

chojecki_2026_poisson_bessel_kernel_bound_planar_sets/: Gives the full Poisson-Bessel kernel proof that, for R at least 1, planar sets in a disk of radius R avoiding positive integer distances have measure at most an absolute constant times the square root of R.

clarkson_1990_combinatorial_complexity_bounds_arrangements_curves_spheres/: Bounds the edges of many cells and vertex degrees in arrangements of lines, circles and spheres, yielding new unit-distance and distinct-distance bounds.

clemen_2025_multiplicities_interpoint_distances/: Settles two Erdos questions on planar distance multiplicities and gives new lower bounds for gaps between the largest multiplicities.

conlon_2015_distinct_volume_subsets/: Improves the lower bound for distinct-distance subsets of n points in d >= 3 dimensions and shows the distinct-volume analog is always polynomial in n.

csizmadia_1994_note_ramsey_type_problem_geometry/: Compiles the eight-point heptagon counterexample and five-point translation proposition, with explicit metric margins and the external disk-covering input.

dumitrescu_2006_distinct_distances_vertex_convex_polygon/: Proves that n points in convex position in the plane include a point with at least ⌈(13n-6)/36⌉ distinct distances to the others.

dumitrescu_2008_distinct_distances_points_general_position/: Constructs n planar points with no three collinear, no four concyclic and no parallelogram that determine only O(n^2/sqrt(log n)) distinct distances, and bounds the largest subset of n points with all distances distinct on the line and in the plane.

dumitrescu_2009_extremal_problems_triangle_areas_two_three/: Bounds the number of unit-area, minimum-area and maximum-area triangles spanned by point sets in the plane and in three-space.

dumitrescu_2019_product_inequality_extreme_distances/: Proves the Erdos-Pach conjecture that minimum and maximum distance multiplicities among n planar points multiply to at most nine eighths n squared.

edelsbrunner_1991_lower_bound_number_unit_distances_convex_polygon/: Constructs, for every n at least 4, a convex n-gon whose vertices determine 2n-7 unit distances, improving the earlier lower bound of Erdos and Moser once n is at least 17.

erdos_1946_sets_distances_points/: Gives first bounds for the fewest distinct distances and the most repeated distances among n planar points, and raises the convex-polygon conjectures.

erdos_1960_sets_distances_points_euclidean_space/: Determines the asymptotic maximum number of times one distance can repeat among n points in dimension four and above.

erdos_1967_applications_graph_theory_geometry/: Determines the maximum number of equal distances among n points in Euclidean space of even dimension at least four for large n, exactly when twice the dimension divides n and otherwise up to half the dimension.

erdos_1970_distinct_distances_between_lattice_points/: Bounds the largest set of lattice points in an n by n grid with all mutual distances distinct between n to the two-thirds minus epsilon and n over log n to the quarter.

erdos_1971_extremal_problems_geometry/: Bounds the number of equal-area triangles and simplices spanned by n points, and states without proof bounds on the number of point quadruples with a repeated distance.

erdos_1975_problems_elementary_combinatorial_geometry/: Survey of combinatorial geometry covering distinct-distance minima, distinct-distance Ramsey numbers, ordinary lines and related extremal questions.

erdos_1983_combinatorial_problems_geometry/: Erdős's 1982 lecture transcript on problems in combinatorial geometry: ordinary lines, integer distances, Euclidean Ramsey sets, convex and empty convex polygons, unit and distinct distances, and the distance-multiplicity question with Pomerance's five-point construction.

erdos_1984_old_new_problems_combinatorial_geometry/: A survey of Erdos's problems on Heilbronn triangles, ordinary lines, convex polygons and the multiplicities of distances among planar points.

erdos_1985_problems_results_combinatorial_geometry/: A problem survey in combinatorial geometry, in six sections, that records the state of the unit-distance and distinct-distance problems with the prizes offered for them, and problems on lines, the unit-distance graph, Heilbronn's triangle problem, Euclidean Ramsey sets and further questions.

erdos_1989_problem_leo_moser_about_repeated_distances/: Disproves Leo Moser's conjecture by constructing sphere point sets in which a fixed distance recurs far more often than linearly.

erdos_1994_postscript_distances_convex_gons/: Determines exactly the longest run of successively farther vertices guaranteed in every convex polygon on n vertices, namely the floor of n over three plus one for n at least 4.

erdos_1994_some_problems_number_theory_combinatorics_combinatorial_geometry/: A problem paper posing open questions in number theory, graph theory and combinatorial geometry, among them the bounded-representation sumset question, the unit distance conjecture, the equilateral triangle in minimal-diameter sets and distinct distances in general position.

erdos_fishburn_1995_multiplicities_interpoint_distances_finite_planar_sets/: Studies the multiplicity vectors of interpoint distances in finite planar sets, settles small cases, and records the conjecture, noted earlier by Erdős and Pach, that some distance other than the diameter occurs at most n times.

erdos_fishburn_1996_maximum_planar_sets_that_determine_k_distances/: Determines the largest planar sets with exactly k distinct distances for k <= 4 (g(2)=5, g(3)=7, g(4)=9) with their extremal configurations, and proves g(5)=12.

feng_2026_semi_autonomous_mathematics_discovery_gemini_case/: Reports thirteen Erdős problems addressed by a Gemini-based research agent with expert vetting, four of them by apparently new proofs.

fishburn_1995_convex_polygons_few_intervertex_distances/: Classifies up to similarity the convex polygons whose number of distinct intervertex distances equals or just exceeds Altman's lower bound of floor(n/2).

fox_2016_more_distinct_distances_local_conditions/: Proves that n planar points any p of which determine at least binom(p,2)-p+6 distinct distances determine at least n^(8/7-o(1)) distinct distances, and records the known bounds for the no-isosceles case D(n,3,3).

furedi_1990_maximum_number_unit_distances_convex_n_gon/: Proves that a convex polygon with n vertices determines at most order n log n unit distances.

gasarch_2025_monochromatic_unit_squares_exposition_open_problems/: Expository column giving full proofs that every 2-coloring of R^4 contains a monochromatic unit square, plus bounds for more colors that the authors describe as apparently new.

ge_2026_two_distance_set_277_points_23_dimensions/: Constructs a 277-point two-distance set in R^23 from the regular two-graph on 276 vertices and records the regular-simplex midpoint construction.

ghosal_2025_subsets_lattice_cubes_avoiding_affine_spherical_degeneracies/: Gives deletion-method lower bounds for subsets of the lattice cube avoiding affine, linear and spherical degeneracies, including, for large n, at least 7n/12 points of the n by n grid with no four collinear or concyclic.

graham_1994_recent_trends_euclidean_ramsey_theory/: Surveys Euclidean Ramsey theory: Ramsey and sphere-Ramsey sets, density theorems, chromatic numbers, and fixed-dimension partition results.

graham_2004_euclidean_ramsey_theory/: Handbook chapter surveying Euclidean Ramsey theory, including r-Ramsey configurations, Ramsey sets, chromatic numbers, and asymmetric variants.

graham_2010_open_problems_euclidean_ramsey_theory/: Surveys open problems in Euclidean Ramsey theory: triangle colorings, which sets are Ramsey, unit-distance graphs, and chromatic numbers.

grayzel_2026_solution_problem_erdos_concerning_distances_points/: Constructs n-point planar sets in which every four points span at least three distances yet only about n over the square root of log n distances occur in total.

greenfeld_2024_integer_distance_sets/: Shows every planar integer distance set is either polylogarithmically small or has all but very few points on one line or circle.

guth_2015_erdos_distinct_distance_problem_plane/: Proves that N points in the plane determine at least cN/log N distinct distances, giving the sharp exponent in Erdős's distinct-distance problem.

ho_2026_erdos_s_diameter_conjecture_separated_distances/: Disproves the dimension-free conjecture that n points whose pairwise distances differ by at least 1 must have diameter at least (1+o(1)) n^2.

janzer_2024_tight_bounds_intersection_reverse_sequences_edge/: Removes the logarithmic factor from the Marcus-Tardos bound on intersection-reverse sequences, improving point-circle incidence and cutting bounds.

juhasz_1979_ramsey_type_theorems_plane/: Proves that every red-blue coloring of the plane with no blue unit distance has a red congruent copy of every four-point configuration, and gives a twelve-point configuration for which this fails.

katz_2004_new_entropy_inequality_erdos_distance_problem/: Combines entropy inequalities to show that any n planar points include a point with Omega(n^{(48-14e)/(55-16e)-eps}) distinct distances to the others, an exponent of about 0.8641.

kovacs_2024_note_erdos_s_mysterious_remark/: Gives a computer-algebra proof that the only 6-point planar set with all triples isosceles is the regular pentagon plus its center.

kreisel_2008_there_are_integral_heptagons_no_three/: Exhaustive computer search finds a seven-point plane set with pairwise integral distances, no three collinear and no four concyclic, of minimal diameter 22270, and a restricted search finds a second one.

mathialagan_2021_bipartite_distinct_distances_plane/: Proves a square-root-of-mn over log n bipartite distance lower bound for m between the cube root of n and n, and treats smaller m separately.

moree_2006_two_dimensional_lattices_few_distances/: Proves that among all planar lattices of covolume one the hexagonal lattice determines asymptotically the fewest distinct distances.

mysticflounder_2026_shared_radius_residual/: A preserved conditional proof announcement and later qualification, documenting the shared-radius residual without establishing Problem 97.

myzelev_2024_characterization_colorings_obtained_method_szlam/: Characterizes the ordered Szlam colorings, those that Szlam's lemma produces once an ordering of F fixes every choice, as exactly the colorings dominant with respect to some ordering of the colors.

nivasch_2013_number_distinct_distances_vertex_convex_polygon/: Improves the lower bound for the largest number of distinct distances from some vertex of a convex n-gon to (13/36 + eps)n - O(1) with eps about 1/23000.

openai_2026_higher_dimensional_erdos_distinct_distances_conjecture/: A 103-page manuscript claiming that for every fixed d at least 3, any n ≥ 2 distinct points in d-dimensional space determine at least c_d n^(2/d) distinct distances, by a contradiction argument over polynomial degree scales, rigid-motion pair flats and a uniform concentration theorem; it bears on Problems 1083, 660 and 89.

openai_2026_power_saving_planar_unit_distances/: Claims the planar unit-distance count is O(n^beta) for an absolute beta < 4/3, by random cuttings, an entropy prediction lemma, number-field heights and an algebraic-independence obstruction; a claimed d = 2 upper bound for Problem 1085, compared against the disproved Problem 90.

openai_2026_weak_pinned_planar_distance_theorem/: Claims the weak pinned planar distinct-distance conjecture: for every fixed s > 0 the fraction of ordered pairs (x, y) of an n-point planar set whose distance from x is repeated at least n^s times tends to zero, so for every fixed eps > 0 all but o(n) points see at least n^{1-eps} distinct distances; proved by contradiction through an extremal graph, a product-formula identity over a number field with nested grid partitions, a variance estimate, tree transport and a Mobius-map obstruction; no rate. Bears on Problem 604.

pach_2002_isosceles_triangles_determined_planar_point_set/: Bounds the number of isosceles triangles spanned by n points in the plane by about n to the power 2.137.

petrov_2021_remark_sets_few_distances/: Gives a short new proof of the Bannai-Bannai-Stanton bound that an s-distance set in R^d has at most binom(d+s,s) points.

raz_2017_number_unit_area_triangles_plane_theme/: Bounds the number of unit-area triangles spanned by n planar points by O(n^{20/9}) and treats two special configurations.

sallerk_2026_convex_nonagon_relations/: A preserved forum coordinate claim and an independently reviewed exact convex E3 nonagon realizing the relations printed in Er87b.

shaffaf_2018_solution_erdos_ulam_problem_rational_distance/: Proves, assuming the Bombieri-Lang conjecture, that no dense subset of the plane has all pairwise distances rational.

sheffer_2014_distinct_distances_open_problems_current_bounds/: Surveys the many variants of Erdos' distinct distances problem and records the best known bounds and open problems for each.

shinohara_2004_classification_three_distance_sets_two_dimensional_euclidean_space/: Classifies the planar three-distance sets: exactly 34 five-point sets up to similarity, none with more than seven points, and the maximal ones.

shinohara_2008_uniqueness_maximum_planar_five_distance_sets/: Proves that the Erdős–Fishburn 12-point configuration is the unique maximum planar five-distance set, via a classification of 8-point four-distance sets.

solymosi_2008_near_optimal_bounds_erdos_distinct_distances_high_dimensions/: Proves by a recursion on the dimension that n points in d-dimensional space determine Omega(n^(2/d - 2/(d(d+2)))) distinct distances for d at least 4, and Omega(n^0.5643) for d = 3, from the planar bound of Tardos.

solymosi_2010_question_erdos_ulam/: Shows lines and circles are the only irreducible real algebraic curves containing an infinite set of points with all pairwise distances rational.

sothanaphan_2026_compact_poissonbessel_proof_integer_distance_free/: Streamlined proof that, for R at least 1, a measurable planar set in a disc of radius R with no two distinct points at a positive integer distance has measure at most a constant times the square root of R.

swanepoel_2004_unit_distance_problem_spheres/: Constructs n points on any sphere of diameter above one spanning at least cn times the square root of log n unit distances.

swanepoel_2009_unit_distances_diameters_euclidean_spaces/: Shows that in dimension four and above, for all sufficiently large n, the maximum numbers of unit distances and of diameters among n points are attained only by Lenz configurations.

swanepoel_2013_favorite_distances_high_dimensions/: Determines the error term and the extremal configurations for the maximum number of favorite-distance pairs among n points in dimension at least four.

szlam_2001_monochromatic_translates_configurations_plane/: Shows every red-blue plane coloring with no unit distance in blue has a red translate of every three-point set, and gives a seven-point counterexample.

tao_2024_planar_point_sets_forbidden_4_point/: Constructs large planar grid subsets avoiding eight four-point distance patterns; Remark 1.8 also asserts no three collinear and no four concyclic.

vesztergombi_1987_bounds_number_small_distances_finite_planar_set/: Bounds the multiplicities of the smallest distances in a finite planar set.

vesztergombi_1987_large_distances_planar_sets/: Proves the bound n_2 <= 3n/2 for the number of pairs at the second largest distance among n points in the plane, with a construction it states attains the bound.

This folder holds sources whose primary subject is Distance Problems.

Sources with other primary subjects

Explicit links to this subject's problems support these cross-references.

Linked from (89)

Graph