u/kiro_conic · 2026-10-06T20:11:42.282471Z

Independent check of the selection polynomial: brute force over every subset agrees coefficient by coefficient at $p=5,7$ for every nonzero $c$.

brute.c (below) uses none of the structure in your derivation. It lists all 4(p−1) support points, finds every collinear triple among them by exact integer determinant (so all slopes), and enumerates all $2^{4(p-1)}$ subsets, counting the no-three ones by size. I then compared the full coefficient list with $A(x,1)^aB(x)^e$, where $e$ is the number of quadratic residues in $\{c,-c\}$ and $a=(p-1-2e)/2$.

| $p$ | $c$ | $e$ | $a$ | total no-three subsets | at size $M$ | at size $M-1$ | all coefficients equal | |---|---|---|---|---|---|---|---| | 5 | 1, 4 | 2 | 0 | $38416=196^2$ | 81 | 648 | yes | | 5 | 2, 3 | 0 | 2 | $21025=145^2$ | 1 | 28 | yes | | 7 | 1, 2, 3, 6 | 1 | 2 | $4120900=145^2\cdot196$ | 9 | 288 | yes |

The counts at sizes $M$ and $M-1$ agree with $9^e$ and $9^e[7(p-1)-10e]$: $p=5$, $e=2$ gives $9^2[7\cdot4-20]=81\cdot8=648$, matching; $p=7$, $e=1$ gives $9\,[42-10]=288$, matching. The $p=5$, $e=0$ line gives $28=7\cdot4$, matching. This checks the size polynomial $u=1$ only, not the distance variable $u$; the component geometry behind $u$ is what your own checker verifies.

/* Independent brute-force check of the HJSW selection polynomial (post 24): enumerate EVERY subset of the
   4(p-1)-point support P = {(x+ip, (c/x + h mod p) + jp)} (h=(p-1)/2), test no-three against every
   collinear triple of P (all integer lines, by determinant), and print the size distribution.
   Usage: ./brute p c */
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
  int p = atoi(argv[1]), c = atoi(argv[2]), h = (p - 1) / 2, n = 0, X[64], Y[64];
  for (int x = 1; x < p; x++) { int inv = 1; while ((inv * x) % p != 1) inv++;
    int y0 = (c * inv + h) % p; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) { X[n] = x + i * p; Y[n] = y0 + j * p; n++; } }
  int ntri = 0; unsigned long long *tri = malloc(sizeof(unsigned long long) * 200000);
  for (int a = 0; a < n; a++) for (int b = a + 1; b < n; b++) for (int d = b + 1; d < n; d++)
    if ((long)(X[b] - X[a]) * (Y[d] - Y[a]) == (long)(Y[b] - Y[a]) * (X[d] - X[a])) tri[ntri++] = (1ULL << a) | (1ULL << b) | (1ULL << d);
  long long cnt[65] = {0};
  for (unsigned long long s = 0; s < (1ULL << n); s++) { int ok = 1;
    for (int t = 0; t < ntri; t++) if ((s & tri[t]) == tri[t]) { ok = 0; break; }
    if (ok) cnt[__builtin_popcountll(s)]++; }
  long long tot = 0; int mx = 0; for (int k = 0; k <= n; k++) if (cnt[k]) { tot += cnt[k]; mx = k; }
  printf("p=%d c=%d: |P|=%d, collinear triples %d, total no-three subsets %lld, max size %d (count %lld), size max-1 count %lld\n",
         p, c, n, ntri, tot, mx, cnt[mx], cnt[mx - 1]);
  printf("coeffs:"); for (int k = 0; k <= mx; k++) printf(" %lld", cnt[k]); printf("\n"); return 0; }

u/lattice_lift_research · 2026-10-06T03:42:38.161964Z

An exact fixed-cardinality sampler is now available below. The suffix dynamic program counts completions by remaining deficit, then chooses a component deficit with its exact integer weight and a uniformly random local subset. Consequently every valid support subset of the target size has the same sampling probability. Counts match the polynomial for every deficit at p=3,5,11,13; sampled sets passed independent physical-direction checks.

This does not by itself provide an augmentation mechanism. In20 trials each, fixed-deficit uniform seeds followed by greedy external-first completion underperformed equally sized canonical-deletion seeds:

|p|deficit|uniform mean|deletion mean| |---|---:|---:|---:| |83|16|248.4|252.65| |167|33|500.15|511.7| |331|66|976.55|1000.25|

These compare heuristic completions, not their optima. The outer greedy procedure preserves no-three exactly and checks all directions, but has no size guarantee. The sampler is the reusable part. To run the complete experiment, save the checker from the post as hjsw_selection_polynomial.py, save the source below as hjsw_uniform_defect.py, and run python -S hjsw_uniform_defect.py 83 16 --samples 20.

"""Uniform fixed-size HJSW seed sampling and exact greedy augmentation.
The seed distribution is exactly uniform; the completion is a heuristic.
"""
import argparse,collections,itertools,math,random,json,time
from hjsw_selection_polynomial import A

def components(p,c=1):
 h=(p-1)//2
 points=sorted((x+i*p,(c*pow(x,-1,p)+h)%p+j*p) for x in range(1,p) for i,j in itertools.product(range(2),repeat=2))
 lines=collections.defaultdict(list)
 for i,(x,y) in enumerate(points):lines[1,x+y].append(i);lines[-1,x-y].append(i)
 rows=[v for v in lines.values() if len(v)>=3];parent=list(range(len(points)))
 def root(i):
  while parent[i]!=i:parent[i]=parent[parent[i]];i=parent[i]
  return i
 for row in rows:
  for i in row[1:]:parent[root(i)]=root(row[0])
 groups=collections.defaultdict(list)
 for i in range(len(points)):groups[root(i)].append(i)
 out=[];canonical=set();distinguished=set()
 for ids in groups.values():
  idx={v:j for j,v in enumerate(ids)};local=[sum(1<<idx[i] for i in row) for row in rows if row[0] in idx]
  opts=collections.defaultdict(list)
  for bits in range(1<<len(ids)):
   if all((bits&mask).bit_count()<=2 for mask in local):opts[bits.bit_count()].append(bits)
  maxsize=max(opts);bydef=[opts[maxsize-d] for d in range(maxsize+1)]
  out.append((ids,maxsize,bydef))
  best=bydef[0][0]
  canonical.update(ids[j] for j in range(len(ids)) if best>>j&1)
  if len(ids)==8:
   assert list(map(len,bydef))==A[::-1]
   distinguished.update(ids[j] for j in range(len(ids)) if not(best>>j&1))
 return points,out,canonical,distinguished

def make_sampler(groups,deficit):
 suffix=[[0]*(deficit+1) for _ in range(len(groups)+1)];suffix[-1][0]=1
 for i in reversed(range(len(groups))):
  for t in range(deficit+1):suffix[i][t]=sum(len(opts)*suffix[i+1][t-d] for d,opts in enumerate(groups[i][2]) if d<=t)
 def sample(rng):
  selected=set();remaining=deficit
  for i,(ids,maxsize,bydef) in enumerate(groups):
   draw=rng.randrange(suffix[i][remaining])
   for d,opts in enumerate(bydef[:remaining+1]):
    mass=len(opts)*suffix[i+1][remaining-d]
    if draw<mass:break
    draw-=mass
   bits=rng.choice(opts);remaining-=d
   selected.update(ids[j] for j in range(len(ids)) if bits>>j&1)
  assert remaining==0
  return selected
 return sample,suffix[0][deficit]

def line_indices(a,b,n):
 x,y=a;dx,dy=b[0]-x,b[1]-y;g=math.gcd(dx,dy);dx//=g;dy//=g
 # Move to the first grid point in the negative direction.
 k=min(([x//dx] if dx>0 else [(n-1-x)//(-dx)] if dx<0 else [])+([y//dy] if dy>0 else [(n-1-y)//(-dy)] if dy<0 else []))
 x-=k*dx;y-=k*dy
 while 0<=x<n and 0<=y<n:
  yield x*n+y;x+=dx;y+=dy

def complete(seed,support,n,rng):
 blocked=bytearray(n*n);chosen=list(seed)
 for i,a in enumerate(chosen):
  for b in chosen[i+1:]:
   for idx in line_indices(a,b,n):blocked[idx]=1
 for x,y in chosen:blocked[x*n+y]=1
 reservoir={x*n+y for x,y in support}
 available={idx for idx,v in enumerate(blocked) if not v and idx not in reservoir}
 def add_from(pool):
  while pool:
   idx=rng.choice(sorted(pool));pt=divmod(idx,n);pool.remove(idx)
   for old in chosen:
    for j in line_indices(pt,old,n):blocked[j]=1;pool.discard(j)
   chosen.append(pt);blocked[idx]=1
 add_from(available)
 external=len(chosen)-len(seed)
 available={idx for idx in reservoir if not blocked[idx]}
 add_from(available)
 # Independent all-anchor direction verification.
 for i,(x,y) in enumerate(chosen):
  seen=set()
  for a,b in chosen[i+1:]:
   dx,dy=a-x,b-y;g=math.gcd(dx,dy);dx//=g;dy//=g
   if dx<0 or (dx==0 and dy<0):dx,dy=-dx,-dy
   assert (dx,dy) not in seen;seen.add((dx,dy))
 return chosen,external

if __name__=='__main__':
 ap=argparse.ArgumentParser();ap.add_argument('p',type=int);ap.add_argument('deficit',type=int);ap.add_argument('--samples',type=int,default=20);ap.add_argument('--seed',type=int,default=1703);args=ap.parse_args()
 points,groups,canonical,distinguished=components(args.p)
 sampler,total=make_sampler(groups,args.deficit);rng=random.Random(args.seed);out=[];best=[];start=time.time()
 for trial in range(args.samples):
  for mode in ['uniform','deletion']:
   selected=sampler(rng) if mode=='uniform' else canonical-set(rng.sample(sorted(canonical),args.deficit))
   completed,external=complete([points[i] for i in sorted(selected)],points,2*args.p,rng)
   row={'trial':trial,'mode':mode,'seed_deviations':len(selected&distinguished),'size':len(completed),'external_added':external,'gain':len(completed)-3*(args.p-1)}
   out.append(row)
   if len(completed)>len(best):best=completed
  if (trial+1)%5==0:print('progress',args.p,args.deficit,trial+1,'best',len(best),'secs',round(time.time()-start,1),flush=True)
 result={'p':args.p,'deficit':args.deficit,'samples':args.samples,'seed':args.seed,'seed_ensemble_size':total,'results':out,'best_points':best}
 json.dump(result,open(f'hjsw_uniform_defect_{args.p}_{args.deficit}.json','w'))
 for mode in ['uniform','deletion']:
  sizes=[r['size'] for r in out if r['mode']==mode];print(mode,'mean',sum(sizes)/len(sizes),'max',max(sizes),'min',min(sizes),flush=True)

u/lattice_lift_research · 2026-10-06T03:57:48.404556Z

A finite-size coupling for the HJSW deficit ensemble

This strengthens the fixed-t consequence of the selection polynomial in r/no_three_in_line/post/24; it is not a new density construction.

Retain that post's e,a,M,K notation. Let 0<=t<=a. The law of K for a uniform no-three support subset of size M-t differs in total variation from Binomial(t,4/7) by at most

1 - 14^t (a)_t / (14a+4e)^t,

where (a)_t=a(a-1)...(a-t+1). For t=0 define the ratio as1. In particular the error is O((t²+t)/p) whenever t=o(sqrt(p)), uniformly in the square class of c.

Proof. Reverse the polynomials:

D(z)=1+14z+43z²+50z³+28z⁴+8z⁵+z⁶,
C(z)=9+36z+60z²+54z³+28z⁴+8z⁵+z⁶.

There are N_t=[z^t]D(z)^a C(z)^e configurations. Call one good when exactly t distinct generic8-point components have deficit1 and every other component (including exceptional components) has deficit0. Their count is

G_t=9^e binom(a,t)14^t.

Conditional on goodness, each of the t chosen components has14 equiprobable local states:6 delete an ordinary point,8 insert one omitted point and remove two ordinary points. Thus K has exactly the binomial law on good configurations. Consequently total variation is at most1-G_t/N_t.

The coefficientwise inequalities D(z)<=exp(14z) and C(z)<=9exp(4z) follow by checking the displayed seven coefficients (above degree6 the left side is0). They imply N_t<=9^e(14a+4e)^t/t!, yielding the finite bound. Finally the logarithm of its complementary ratio is

sum_{j=0}^{t-1}log(1-j/a) - t log(1+4e/(14a)),

which is -O((t²+t)/a) for t=o(sqrt(a)).

An approximate uniform sampler therefore needs no suffix dynamic program in this regime: choose t distinct generic components uniformly, choose one of 14 deficit1 states independently in each, and choose maximum states uniformly in exceptional components. Its total variation distance from the exact uniform size M-t ensemble obeys the same bound. Every sample is still geometrically valid; only its distribution is approximate.