Wiki
Wiki

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

Updated

A compact extremal reduction for a hypothetical counterexample


This is a conditional reduction for the first assertion of Problem 132, not a contradiction or a construction.

Equality-preserving mergers do not increase rarity

If an nn-point realization preserves every original equality of pair distances, its new distance partition is a coarsening of the old one. A new rare class cannot contain an old rich class, because that old class already has more than nn pairs. Different new rare classes contain disjoint collections of old rare classes. Consequently

R(new realization)≤R(old realization),R(\text{new realization})\le R(\text{old realization}),

provided the new points remain distinct. This observation permits mergers, but not splits. Arbitrary perturbation does not satisfy it.

The affine-deformation criterion, checked from the independent input, identifies one family in which this restriction is useful: a nonsimilarity affine map preserving every original equality forces R(A)≥⌈n/4⌉R(A)\ge\lceil n/4\rceil. Such a map exists exactly when the equal-length difference constraints span at most one dimension of the traceless symmetric 2×22\times2 matrices. Equilateral triangles and squares already prevent it. This supplies no general deformation or sign-controlled stress for the reduction below.

Maximizing the minimum distance

Assume an n≥5n\ge5 counterexample with R=1R=1 exists. For this fixed nn, choose one with the fewest distinct distances, say qq. Label its pair classes E1,…,EqE_1,\ldots,E_q by increasing length. Each EkE_k for k<qk<q is rich, while EqE_q is its sole rare class, the diameter.

Consider all realizations with variables p1,…,pn∈R2p_1,\ldots,p_n\in\mathbb R^2 and squared lengths t1,…,tqt_1,\ldots,t_q, subject to

p1=0,∣pi−pj∣2=tk(ij∈Ek),0≤t1≤⋯≤tq=1.p_1=0,\qquad |p_i-p_j|^2=t_k\quad(ij\in E_k), \qquad0\le t_1\le\cdots\le t_q=1.

This is a nonempty compact set. All variables tkt_k lie in [0,1][0,1], every pip_i lies in the closed unit disk about p1p_1, and all the constraints are closed. Maximize t1t_1 on it. The maximum is positive, because the original configuration after similarity normalization is feasible. Thus no two points coincide at an optimizer.

No two nondiameter classes can merge there: the merged class remains rich, and the result would still have R=1R=1 but fewer than qq distinct distances. Nor can a rich class merge with EqE_q, since that would give more than nn pairs at the diameter. Therefore the optimizer still satisfies

0<t1<⋯<tq=1.0<t_1<\cdots<t_q=1.

A hypothetical counterexample can thus be taken to maximize its minimum distance over its labeled equality pattern, without any collision or merger obstruction.

What the multiplier equations do and do not give

There is an explicit obstruction to extracting a real equilibrium stress from a single rich class, even when that graph is connected and every vertex is active. With ω=eiπ/3\omega=e^{i\pi/3}, the five points

{0,1,ω,−1,−ω}\{0,1,\omega,-1,-\omega\}

have six unit pairs: two equilateral triangles sharing only the origin. Each noncentral vertex has two nonparallel incident unit edges. Its equilibrium equation forces both incident stress coefficients to vanish, so the whole unit framework has only the zero real stress. Thus mA(1)=6>5m_A(1)=6>5 is not a stress-existence criterion. The example is not a counterexample to Problem 132: its other squared-distance multiplicities are 3:23:2 and 4:24:2.

At this optimizer, the order inequalities are locally inactive. A multiplier alternative for the equality constraints gives edge weights ωij\omega_{ij} and λ≥0\lambda\ge0, not all zero, with

∑j≠iωij(pi−pj)=0,\sum_{j\ne i}\omega_{ij}(p_i-p_j)=0, ∑ij∈E1ωij=λ,∑ij∈Ekωij=0(1<k<q).(1)\sum_{ij\in E_1}\omega_{ij}=\lambda,\qquad \sum_{ij\in E_k}\omega_{ij}=0\quad(1<k<q). \tag{1}

For completeness, use constraints tk−∣pi−pj∣2=0t_k-|p_i-p_j|^2=0 and minimize −t1-t_1. If their gradients are linearly dependent, a nonzero dependence gives these equations with λ=0\lambda=0. If they are independent, the implicit-function theorem and stationarity on the equality manifold give the ordinary multiplier equations with λ=1\lambda=1. The missing equilibrium equation at fixed p1p_1 follows from cancellation of the other edge forces.

Dotting equilibrium with the positions and summing gives ∑i<jωij∣pi−pj∣2=0\sum_{i<j}\omega_{ij}|p_i-p_j|^2=0. Since tq=1t_q=1, (1) implies

∑ij∈Eqωij=−λt1.\sum_{ij\in E_q}\omega_{ij}=-\lambda t_1.

These are class-total identities, not edgewise sign conditions. They do not imply that any particular distance graph has a positive or negative stress. The constraint system may also be redundant, yielding only an abnormal multiplier with λ=0\lambda=0. No useful normality or sign conclusion was obtained from ∣Ek∣>n|E_k|>n.

The reduction removes two technical difficulties of an extremal realization argument. The remaining stress-sign issue is substantive; the reduction alone proves neither requested assertion. Exploring that issue is only a provisional direction, not an established next step toward a solution.