Pith. Sign in

REVIEW

On the number of two-dimensional threshold functions

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Max A. Alekseyev

Combinatorics · Submitted 23 Feb 2006 · 18 references

Pith's verdict: Exact enumeration of 2D threshold functions via a clean stable/unstable line count; a solid paper, only minor proof gaps, deserves a serious referee.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 28, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 1 major objection · 5 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv IDmath/0602511 (version 4)
Pith ID6GFD2OIV, Pith's permanent record of this paper and its review
CitationMax A. Alekseyev. "On the number of two-dimensional threshold functions." arXiv:math/0602511 (2006). https://pith.science/paper/6GFD2OIV
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

The paper proves that the number of line-separable two-colorings of an m×n integer grid is (2m+1)(2n+1)+1+4V(m,n), with V a coprime-pair sum, and derives the asymptotic 6/π² k⁴ + O(k³ ln k) for the square case.

The reading

The paper solves the exact enumeration of two-dimensional threshold functions — two-colorings of the integer points of a rectangle that a straight line can separate into the two colors — a problem for which only asymptotic bounds were previously known. The exact count is $N(m,n)=(2m+1)(2n+1)+1+4V(m,n)$, where $V(m,n)$ sums $(m+1-i)(n+1-j)$ over pairs $1\le i\le m$, $1\le j\le n$ with $\gcd(i,j)=1$. For a $k\times k$ grid this becomes $P(k,2)=(2k-1)^2+1+4\sum_{\gcd(i,j)=1}(k-i)(k-j)$, with leading asymptotic $\frac{6}{\pi^2}k^4+O(k^3\ln k)$. The proof is a geometric census: every separable coloring is stable or unstable, and each class is counted by lines through grid points. Exact counts of threshold functions are rare, so reducing the entire two-dimensional case to one coprime-weighted sum is the kind of result that makes neighboring enumeration problems look tractable.

What carries the argument

The load-bearing object is the stable/unstable decomposition of threshold functions, with unstable functions counted through $u$-stable lines: a line through the vertex $u$ that also passes through another lattice point of the rectangle. The key identity is Lemma 22's $V(t,k-1)+V(t,k)=2V(t,k-1/2)$, together with the relations $V(t,k)=\sum_{p\le t}\sum_{q\le k}U(p,q)$ and $U(t,k)=V(t,k)-V(t,k-1)-V(t-1,k)+V(t-1,k-1)$, where $U$ counts coprime pairs. These identities collapse the four parity cases for the number of $u$-stable lines into the single expression $2(mn-1)+8V((m-1)/2,(n-1)/2)$, converting a geometric rotation-count into one weighed sum over coprime pairs.

Extended reading notes

Core claim

On its own terms, the paper establishes the exact formula $N(m,n)=(2m+1)(2n+1)+1+4V(m,n)$ for the number of two-dimensional threshold functions on an $(m+1)\times(n+1)$ lattice rectangle, with $V(m,n)=\sum_{1\le i\le m,\,1\le j\le n,\,\gcd(i,j)=1}(m+1-i)(n+1-j)$. For the square grid this gives $P(k,2)=(2k-1)^2+1+4\sum_{1\le i,j\le k-1,\,\gcd(i,j)=1}(k-i)(k-j)$, and the same machinery yields $P(k,2)=\frac{6}{\pi^2}k^4+O(k^3\ln k)$. The argument separates threshold functions into stable ones (defined by a line through at least two lattice points) and unstable ones (all defining lines pass through a single vertex), counts unstable functions by the number of 'u-stable' lines through each possible vertex, counts stable functions by primitive direction vectors $(a,b)$ with $\gcd(a,b)=1$, and then reassembles both counts through identities on coprime-pair sums. The exact split of the total into stable and unstable counts is part of the result, not just a device.

Load-bearing premise

The enumeration of the unstable functions assumes that every non-stable separating line through a grid point lies between two adjacent stable lines and, apart from the special line through the origin, defines a distinct function; if two different lines ever gave the same coloring, the unstable total would be off.

Editorial extensions

If this is right

  • For every square grid, the exact count is $P(k,2)=(2k-1)^2+1+4\sum_{1\le i,j\le k-1,\,\gcd(i,j)=1}(k-i)(k-j)$, so the enumeration problem for two-dimensional threshold functions is closed.
  • The rectangular-grid analogue $N(m,n)=(2m+1)(2n+1)+1+4V(m,n)$ is also exact, so grids with unequal side lengths need no separate treatment.
  • The leading asymptotic constant is $6/\pi^2\approx0.6079$ with error $O(k^3\ln k)$, pinning down the constant that previous bounds left between $3/(8\pi^2)$ and $6/\pi^2$.
  • The separate counts of stable and unstable functions are explicit, and every unstable function has a three-point teaching set, so the only remaining teaching-set question is which stable functions require four points.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same stable/unstable line census could be attempted for other finite point sets — triangular patches, hexagonal grids, or randomly perturbed point clouds — and would likely yield exact counts expressed as sums over primitive direction pairs whenever the point set has enough symmetry.
  • Refining the stable-function count by the location of the separating line relative to the grid center would resolve the paper's open problem of counting minimum teaching sets of size 3 versus 4, since size-4 functions are exactly the stable functions whose complement is also stable.
  • The constant $6/\pi^2$ is the density of coprime integer pairs, so the dominant $k^4$ term says that almost all line-separable colorings are controlled by primitive direction vectors; this suggests analogous leading constants for higher dimensions may be products $\prod_p(1-1/p^d)$ over primes.
  • For rectangular grids with one side much longer than the other, the paper's second asymptotic expresses the count through the summatory totient functions $\Phi$ and $\Psi$, which may connect this enumeration to estimates of visible lattice points in thin strips.
Original abstract

A two-dimensional threshold function of k-valued logic can be viewed as coloring of the points of a k x k square lattice into two colors such that there exists a straight line separating points of different colors. For the number of such functions only asymptotic bounds are known. We give an exact formula for the number of two-dimensional threshold functions and derive more accurate asymptotics.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 2,888 input tokens.

What the abstract itself states, as probabilities: claims first 0.13 · states limitation 0.08 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.52 · compares with prior results 0.74 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v4. Results and the main claim are underlined; .

A two-dimensional threshold function of k-valued logic can be viewed as coloring of the points of a k x k square lattice into two colors such that there exists a straight line separating points of different colors. For the number of such functions only asymptotic bounds are known. We give an exact formula for the number of two-dimensional threshold functions and derive more accurate asymptotics.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 A two-dimensional threshold function of k-valued logic can be viewed as coloring of the points of a k x k square lattice into two colors such that there exists a straight line separating points of different colors. background 1.00 0.10 0.03 asserted 0.98
s1 For the number of such functions only asymptotic bounds are known. gap 0.98 0.04 0.02 asserted 1.00
s2 We give an exact formula for the number of two-dimensional threshold functions and derive more accurate asymptotics. contribution 0.94 0.97 0.93 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read
  • arXiv listing abstract v4
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. Examples of threshold functions defined by the lines
Figure 2. a) The point (wx, wy − 1) belongs to M(`1) \ M(`2), implying that `1 and `2 are not equivalent. b) The line ` lies between the adjacent u-stable lines `1 and `2. The line ` is stable but not u-stable since it has no integer points within the rectangle Ku, except u. integral point and z is the middle point of the interval with integral endpoints, a stronger inequality zy − uy ≥ 1 2 holds. Consider an equation of the line `1 in the form y1(x) = uy−vy ux−vx (x−vx)+vy and an equation of the line ` in the form y(x) = wy−vy wx−vx (x − vx) + vy. Define a function f(x) def = y(x + v

Figures reproduced from arXiv:math/0602511 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.