Wiki
Wiki

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

Updated


This proves the full statement of L190. Write V=RP×RPV=\mathbb R^P\times\mathbb R^P and

ℓu(m,k)=∑v∈PmvLv−kuLu,C={(m,k):mv≥0, ℓu(m,k)≤0 (u,v∈P)}.\ell_u(m,k)=\sum_{v\in P}m_vL_v-k_uL_u, \qquad C=\{(m,k):m_v\ge0,\ \ell_u(m,k)\le0\ (u,v\in P)\}.

Unique factorization implies that Lp,Lq,LrL_p,L_q,L_r are linearly independent over Q\mathbb Q. The coefficient vector of each ℓu\ell_u therefore has rational rank three. Multiplying a vector by a nonzero real scalar preserves this rank: scalar multiplication is a Q\mathbb Q-linear isomorphism between the two coordinate spans. Consequently no nonzero normal of rational rank at most two has the same kernel as ℓu\ell_u.

Fix u∈Pu\in P. There is a relatively open, nonempty part F∘F^\circ of the hyperplane H=ker⁡ℓuH=\ker\ell_u on which every mvm_v is positive and all the inequalities ℓv<0\ell_v<0 for v≠uv\ne u are strict. For example, start at the point with all mv=1m_v=1, with ku=∑vLv/Luk_u=\sum_vL_v/L_u, and with kv=2∑wLw/Lvk_v=2\sum_wL_w/L_v for v≠uv\ne u. A small neighbourhood within HH has the required properties. All its kvk_v are positive as well.

Suppose a proposed finite indicator identity uses the normals a1,…,aMa_1,\ldots,a_M, after listing every defining inequality of every region. Each H∩ker⁡aiH\cap\ker a_i is a proper linear subspace of HH, by the rank observation. Finitely many proper linear subspaces cannot cover a nonempty open subset of HH. Choose x∈F∘x\in F^\circ outside their union.

There is a ball UU around xx in VV on which all coordinates mv,kvm_v,k_v are positive, all ℓv\ell_v with v≠uv\ne u are negative, and each aia_i has one fixed, nonzero sign. Both sides of HH meet UU. Choose xin,xout∈Ux_{\rm in},x_{\rm out}\in U with

ℓu(xin)<0<ℓu(xout).\ell_u(x_{\rm in})<0<\ell_u(x_{\rm out}).

For each positive integer NN, round the coordinates of NxinNx_{\rm in} and NxoutNx_{\rm out} to nearest integers, obtaining zin,Nz_{{\rm in},N} and zout,Nz_{{\rm out},N}. The rounding errors are bounded independently of NN. Thus, for any fixed linear form aa,

a⋅zin,N=N(a⋅xin)+O(1),a⋅zout,N=N(a⋅xout)+O(1).a\cdot z_{{\rm in},N}=N(a\cdot x_{\rm in})+O(1), \qquad a\cdot z_{{\rm out},N}=N(a\cdot x_{\rm out})+O(1).

For all sufficiently large NN, both rounded vectors have positive coordinates. Every ℓv(zin,N)\ell_v(z_{{\rm in},N}) is negative, hence less than LvL_v, so zin,N∈Ωz_{{\rm in},N}\in\Omega. In contrast, ℓu(zout,N)>Lu\ell_u(z_{{\rm out},N})>L_u, so zout,N∉Ωz_{{\rm out},N}\notin\Omega.

For every defining inequality with normal aia_i and constant bib_i, the values at these two vectors tend to the same signed infinity. They therefore either both satisfy that inequality or both fail it, whether the comparison is strict or non-strict. Because there are only finitely many inequalities, for all sufficiently large NN the two vectors have identical membership in every region EjE_j. The proposed right-hand side then takes equal values at them, whereas 1Ω\mathbf1_\Omega takes values one and zero. This contradiction proves the indicator assertion.

Finally, the coordinate span of a normal is unchanged by an invertible rational linear transformation: each transformed coefficient is a rational linear combination of the old ones, and the inverse gives the reverse inclusion. Translation changes only the constant term. A product of planar polyhedra, each with only one irrational slope, and rational polyhedra has defining normals of rational rank at most two, even when the slopes differ between the planar factors. The indicator assertion therefore applies to every finite signed partition into their invertible affine rational images.