F(S,T): counting under a sum and a product

How many ordered tuples of nonnegative integers have both a small sum and a small product? The answer changes sharply when we add a coordinate. This article develops exact reductions for two, three and four dimensions, then explains what is still needed for the proposed square-root algorithm in 3D.

You need integer arithmetic, sums and binomial coefficients. The geometric sections also use convex hulls. This is a research note: proved identities, locally reviewed arguments and conditional algorithmic claims are identified separately.

Experiment: Exact counts in 2D, 3D and 4D Experiment: Explore the lattice and its slices

1. What is being counted?

For integers $S,T\geq0$ and fixed dimension $d$, define

$$F_d(S,T)=\#\left\{(x_1,\ldots,x_d)\in\mathbb Z_{\geq0}^d: \sum_{i=1}^d x_i\leq S,\quad \prod_{i=1}^d x_i\leq T\right\}.$$

The coordinates are ordered. Thus $(1,2,3)$ and $(3,2,1)$ are different triples. Both inequalities are weak: a point exactly on either boundary is included. A zero coordinate makes the product zero, so such points satisfy every nonnegative product cap.

The diagonal case sets $S=T=N$. It is a restriction of the same function, not a different definition. The experiment uses the dimension subscript explicitly because $F_2(6,6)=25$, $F_3(6,6)=83$ and $F_4(6,6)=210$.

N	2D: F₂(N,N)	3D: F₃(N,N)	4D: F₄(N,N)
0	1	1	1
1	3	4	5
2	6	10	15
3	10	20	35
4	15	35	70
5	19	56	126
6	25	83	210
7	29	107	326
8	35	141	476
9	40	174	650
10	46	213	868

These are full integer answers. A modular answer means reducing this integer modulo a stated modulus; it is not interchangeable with the full count.

2. Remove the zero coordinates first

Stars and bars gives $\binom{S+d}{d}$ nonnegative tuples with sum at most $S$, and $\binom Sd$ strictly positive ones. Therefore

$$Z_d(S)=\binom{S+d}{d}-\binom Sd$$

counts all tuples having at least one zero, exactly once. We use $\binom Sd=0$ when $S<d$. In particular,

$$Z_2(S)=2S+1,\qquad Z_3(S)=1+\frac{3S(S+1)}2.$$

This subtraction avoids inclusion-exclusion mistakes where coordinate axes and planes overlap. At $S=6$, the three zero planes contribute 64 distinct triples, not three disjoint copies of a triangular grid.

For positive integers, $ab\geq a+b-1$. Repeated application gives

$$\prod_i x_i\geq\sum_i x_i-d+1.$$

Hence the positive tuples may use the shorter sum cap

$$P_d=\min(S,T+d-1).$$

Only the positive part may be shortened. The zero term must retain the original $S$. For example, $F_3(100,1)=15152$: there are 15151 zero-product triples and one positive triple, $(1,1,1)$. Replacing $S=100$ by the positive cap 3 in the zero term would lose almost the entire answer.

3. Exact formulas for small experiments

In two dimensions, fixing $x=a>0$ leaves a single interval for $y$:

$$F_2(S,T)=2S+1+ \sum_{a=1}^{S-1}\max\left(0,\min\left(S-a,\left\lfloor\frac Ta\right\rfloor\right)\right).$$

For triples, fix the first two coordinates:

$$F_3(S,T)=Z_3(S)+ \sum_{a=1}^{S-2}\sum_{b=1}^{S-a-1} \max\left(0,\min\left(S-a-b,\left\lfloor\frac{T}{ab}\right\rfloor\right)\right).$$

These formulas are exact, but direct evaluation is not the proposed fast method. The 2D sum has $O(S)$ columns and the 3D sum has $O(S^2)$ columns. In fixed dimension $d$, the corresponding positive-column reference uses at most $O(S^{d-1})$ columns, with integer arithmetic charged separately.

The browser experiment uses this bounded reference with $S\leq100$. Products and counts in this range fit exactly in JavaScript integers. It evaluates the zero term separately and never runs a native C++ candidate. Its operation count describes this reference implementation only.

Read one slice

In the lattice experiment, a 3D slice fixes $z$. Its accepted points satisfy

$$x+y\leq S-z,\qquad xyz\leq T.$$

For $z>0$, its size is $F_2(S-z,\lfloor T/z\rfloor)$. The $z=0$ slice is different: every point below the sum line is accepted, giving $\binom{S+2}{2}$ points. Thus the exact recurrence is

$$F_3(S,T)=\binom{S+2}{2}+\sum_{z=1}^{S}F_2\left(S-z,\left\lfloor T/z\right\rfloor\right).$$

Try $S=T=6$. The zero slice contains 28 points; the slice $z=1$ contains 21. Summing every slice gives 83. Crosses fail at least one constraint; circles mark accepted zero-product points; squares mark accepted positive points. The display is a lattice slice, not a continuous-area approximation.

4. The diagonal simplifies the sum constraint

Let $D_d(N)$ count ordered positive tuples whose product is at most $N$, without a sum cap. For sufficiently large $N$ relative to fixed $d$, only a small set of these tuples violates the diagonal sum cap. In the dimensions considered here,

$$\begin{aligned} F_2(N,N)&=Z_2(N)+D_2(N)-2 &&(N\geq2),\\ F_3(N,N)&=Z_3(N)+D_3(N)-6 &&(N\geq5),\\ F_4(N,N)&=Z_4(N)+D_4(N)-12 &&(N\geq7). \end{aligned}$$

The removed tuples have one large coordinate and all remaining coordinates equal to one. In 3D, for example, the six exceptions are the three permutations of $(N,1,1)$ and of $(N-1,1,1)$. The thresholds matter; use direct counting below them.

Here is why two nonunit coordinates cannot cause another 3D exception once $N\geq5$. If $a,b\geq2$ and $c\geq1$, then $abc\geq a+b+c$ except at $(2,2,1)$ and its permutations. That exceptional sum is 5, so it also satisfies the sum cap. The same argument in 4D has worst positive difference $\sum x_i-\prod x_i=2$, attained at permutations of $(2,2,1,1)$; its sum is 6, below the stated threshold 7.

An identity in terms of $D_d$ does not determine how quickly $D_d$ can be evaluated. This distinction is central to the research problem.

5. Why the 2D geometry helps

Put $M=T+1$. The excluded positive points have product at least $M$. In the plane, the lower boundary of their integer hull is a decreasing polygonal chain. The positive cap is $P_2=\min(S,M)$.

For a chain edge from $(x_0,y_0)$ to $(x_1,y_1)$, write $a=x_1-x_0$ and $b=y_0-y_1$. Assign the integer columns $x=x_0+k$, $0\leq k<a$, to this edge. Their clipped counts are the positive values of

$$q(k)=P_2-x_0-y_0+1-k+\left\lfloor\frac{bk}{a}\right\rfloor.$$

The half-open interval assigns a shared endpoint to one edge only. Consecutive values change by one of two adjacent integers, so the positive range is an interval. An exact floor-sum procedure can aggregate it without visiting every column.

The local 2D argument combines exact next-vertex search, a near-cube-root bound on the chain size and these clipped floor sums. It reaches a locally proved $\widetilde O((T+1)^{1/3})$ mathematical result; independent external review remains open. The tilde hides logarithmic factors. Reading binary $S$ and performing exact arithmetic remain part of the cost statement.

Equality is not a numerical tolerance. At product threshold 12, the ray $(3,3)+m(1,0)$ is outside at $m=0$ and inside at $m=1$. A continuous root alone is not the discrete first-change rule: the integer endpoint predicates must be checked exactly.

6. What remains in 3D

For triples, the convex complement gives a useful exact reduction. With $M=T+1$ and $P=\min(S,T+2)$, define

$$J_M=\operatorname{conv}\{x\in[1,M]^3\cap\mathbb Z^3:x_1x_2x_3\geq M\}.$$

Then

$$F_3(S,T)=Z_3(S)+\binom P3- \#\{x\in J_M\cap\mathbb Z^3:x_1+x_2+x_3\leq P\}.$$

For $(S,T)=(5,3)$, this reads $46+10-3=53$: the three excluded positive tuples are the permutations of $(1,2,2)$. The identity is exact without any fast-optimization assumption.

The geometric route bounds the number of hull vertices by $O(M^{1/2}\log^2 M)$. A small hull is promising, but counting its vertices is not the same as constructing them. The proposed traversal uses a bounded polygonal section of each vertex's normal cone. It must obtain true optimizing section vertices, certify adjacent edges and recover neighboring primal vertices exactly.

Several construction details are now explicit:

• A vertex is stored with its own integral exposing objective, not merely its coordinates
• Chord refinement publishes a section only after every edge is certified; a section with $m$ edges needs at most $2m+1$ exact section-optimization calls under the provider assumptions
• A process-once schedule assigns each ordinary neighbor call to a distinct directed incidence, giving at most $2E$ such calls under the stated traversal assumptions
• Registry lookup, parsing, copies, rejected inputs and simultaneous live allocations have separate charges

The outstanding issue is the implementation and uniform cost of the exact operations used by that construction. A support value without its attaining vertex is insufficient. An optimizer that enumerates a large region does not inherit the size of its short output. A scalar lattice count does not imply small workspace while the count is being computed.

The square-root claim therefore still requires exact support, exact section optimization and exact rational-cell counting with the promised time, bit size and memory bounds on every generated input. It also needs the stated computational model and lifetime bounds to compose. Finite examples cannot supply these uniform guarantees.

7. Results and their limits

Dimension	General F(S,T)	Diagonal F(N,N)	Current qualification
2D	Exact clipped reduction and local soft-one-third argument	Exact D₂ identity; local cube-root route	Locally proved mathematics; external review open
3D	Exact convex-complement reduction; square-root route depends on exact providers	Exact D₃ identity; accepted 5/9 arithmetic baseline	Square-root route conditional, not an accepted unconditional implementation bound
4D	Exact zero decomposition and slicing	Exact D₄ identity above the threshold	No fast 4D exponent established here

The accepted complete 3D baseline remains $O(T^{5/9})$ in the project's arithmetic-operation accounting. It must not be compared directly with a bit-complexity claim without charging the integer operations. On the diagonal, substitute $T=N$. The proposed $\widetilde O(T^{1/2})$ route is a distinct conditional result, not a timing label for the reference experiment.

Historical measurements are also a separate category. The preserved dataset has 7836 elapsed-time rows for 325 implementation identities, with three repetitions per recorded implementation/input cell. Its answer-track and transformation provenance are incomplete, and CPU and memory fields are absent. It does not establish a current qualified C++ speed ranking. This page deliberately reports no invented benchmark curve.

8. Reading and reproducibility

This article condenses the project's internal research note, especially the counted-set reduction, the planar boundary argument, diagonal identities and the section-construction obligations. The status reflects the current internal reconciliation, not an independent external acceptance.

• Internal source: the project's condensed research summary, for the function definition and status comparison
• Internal source: the extended geometric research note, for the planar chain, normal sections and charged traversal requirements
• The exact reference formulas are in section 3; the experiments use integer-only bounded arithmetic and show the zero and positive contributions separately
• For a boundary check, compare $T=0$ with $T=1$ at $S=3$ in 3D: only $(1,1,1)$ is added
• For a dimension check, keep $S=T=6$ and compare all three results in the exact-count experiment

The experiments are demonstrations and reproducible small-input checks. They do not run the proposed optimization providers, prove the asymptotic bounds or measure the native C++ solvers.