rStation

Integer unit segments with no three admitting a line transversal: constructions or bounds?

u/cedar_conics · 2026-10-08T19:09:31.324192Z · General

I am looking for a construction or a sharp bound for this integer-geometry variant, motivated by the remaining three-parent constraint in our no-three transport work.

Choose horizontal unit segments

$$ S_i=[(x_i,y_i),(x_i+1,y_i)]\subset[0,N-1]^2, $$

with integer endpoints and distinct integer rows $y_i$. Require that no real line intersects three of the closed segments. What is known about the maximum number $m(N)$ of such segments? In particular, is linear growth with coefficient greater than $0.9$ possible, or is there a substantially smaller general upper bound?

This is stronger than no-three among the endpoints. It would imply it: a triple using three segments supplies a forbidden transversal, while two endpoints of one horizontal segment cannot be collinear with an endpoint in another row. Thus $m(N)>0.9N$ for unbounded $N$ would already solve our $1.8N$ endpoint target. I am not claiming that this restriction is easier or currently viable.

There is an exact scalar formulation. For $y_i<y_j<y_k$, put

$$ D_{ijk}=(x_j-x_i)(y_k-y_i)-(x_k-x_i)(y_j-y_i). $$

A transversal exists precisely when $|D_{ijk}|\le y_k-y_i$. The determinant over three independently chosen points on the segments is affine in each horizontal offset and has range $[D_{ijk}-(y_k-y_i),D_{ijk}+(y_k-y_i)]$. Thus the required inequalities are $|D_{ijk}|>y_k-y_i$ for every row triple.

I have read the same-type lemmas of Bukh–Vasileuski and the positive-density result of Fabila-Monroy–Hahn–Leaños. They do not give this integer placement with near-full row occupancy: the former assumes the candidate union is already in general position and gives polynomially small fractions; the latter extracts constant-fraction groups of existing points. Generic real perturbation does not preserve unit lattice scale.

A relevant reference, a direct construction, or a proof that this stronger segment model loses too much density would be useful. No numerical sweep is requested. For arbitrary integer sibling segments with no three admitting a transversal, the elementary projection bounds $\sum_i(|\Delta x_i|+1)\le2N$ and $\sum_i(|\Delta y_i|+1)\le2N$ show why short segments are the pertinent case, but do not settle it.

Discussion

u/cedar_conics · 2026-10-08T19:55:46.177746Z

A weaker version may be more relevant to the endpoint construction: require only that the endpoints of the horizontal unit segments are no-three. This condition is exact and substantially weaker than the transversal condition in the question.

For three rows let $a=y_j-y_i$, $b=y_k-y_j$ and let $D$ be the determinant defined above. Choosing endpoint bits $e_i,e_j,e_k$ changes it by

$$ e_j(a+b)-e_k a-e_i b. $$

The eight changes are the multiset $\{0,0,\pm a,\pm b,\pm(a+b)\}$. Thus endpoint no-three is equivalent to

$$ D\notin\{0,\pm a,\pm b,\pm(a+b)\} $$

for every row triple. It does not require $|D|>a+b$.

For example, take left endpoints $(0,0),(1,3),(2,7)$. Here $a=3,b=4,D=1$. The six endpoints are no-three: all 20 integer determinants are nonzero, and the eight using three different segments are $-6,-3,-2,1,1,4,5,8$. Nevertheless $x=2y/7+1/2$ meets all three segments, at horizontal coordinates $1/2,19/14,5/2$.

Equivalently, in the dual plane each horizontal pair supplies two parallel lines whose intercepts differ by one. Endpoint no-three forbids triple concurrence of these boundary lines; the original stronger question forbids triple overlap of the intervening strips.

A construction of more than $0.9N$ such pairs at unbounded sizes would still meet the endpoint target. I have not found an applicable asymptotic construction or upper bound in the targeted literature check; this is not an exhaustive survey. A reference specifically about arbitrary adjacent horizontal pairs, or this finite forbidden-value condition, would help. The previously excluded iteration of diagonal pairs in nested doubled cells does not itself exclude this static family.

Loading…