Point Counting in Reed-Solomon Codes/Lattices

Point Counting

To count vectors in the intersections of cosets of the "Construction A" lattice from the specified Reed-Solomon code and the specified body.

Code

Field: q = ~ (prime(s) in the range)

Dual dimension: k = ~

Evaluation set (and its order): F^*: (1,…,q-1) F^*: [gen] (1,g,…,g^{q-2}) F^*: shuffle F: (0,1,…,q-1) F: (0,[gen]) F: ([gen],0) F: shuffle
g is the "smallest" generator of F^*

Body

Radius (in ℓ₁): h = 2k 2k-1 2k-2 2k-3 2k-4 constant (if constant: h = )

Center: origin random random by body

Restrictions: entire balanced integer ternary binary ball sphere
`balanced` is ignored for `binary`

Optimization

Cosets/syndromes to count: all syndromes the zero syndrome (0,…,0,a≠0) syndromes (0,…,0,a≠0,0) syndromes (0,…,0,a≠0,b) syndromes (with syndrome starting from degree )

Counting method: direct split in q split in h
`split in q` method is exact and gives same results as `direct`
`split in h` method takes the positive h/2-body self-convolved as the (balanced) h-body; hence it requires h to be even, only counts balanced cosets, and introduces overcounting (strictly) inside the h-sphere even when a sphere body is specified

Limit on number of sample points:

Embedding hypercube in coset

To count the minimum sizes of intersections of cosets and body when fixing (the last) several coordinates to be binary; the minimum is taken over all binary choices. If the minimum size is at least 1 (i.e., for every binary choice, the intersection of coset and body is nonempty), then it means a hypercube can be trivially embedded in the coset.
by default the evaluation set is ordered as (0,1,…,q-1), so the last several coordinates corresponds to the "largest" field elements

Dimension of hypercube:
0 has no effect

Fourier Analysis

To compute the kernel function (at origin) by summing Fourier series.

Field: same q as above

Kernel: self-convolution balanced self-convolution
base function is the indicator function over columns in the parity-check matrix of the Reed-Solomon code with the same k as above
number of (function copies in) self-convolution is the same h as above
`balanced` means half of the copies are instead over minus columns

Experiments

Run Point Counting
`max`, `max2`, `min`, `mean`, `stddev`: statistics of counting over cosets ("max2" is second max, and max2/min is unset if same as max/max2)
`syndromes*`: cosets/syndromes achieving max/max2/min
`samplePoints*`: sample vectors in one (usually the first) coset achieving max/max2/min
for embedding hypercube: `samplePoints*` only includes one sample vector for each binary choice; an extra property `ranges` records the maximum counting besides the minimum for all cosets (similarly, max is unset if same as min); an extra property `samplePointsMaxMin` records the sample vectors for the binary choices achieving the minimum counting

Run Fourier Sum
`max`, `max2`, `min`, `mean`, `stddev`: statistics of sub-sums grouped by the highest dual variable (the dual variable corresponding to the highest-degree syndrome), thus over its q values
`sum`: the entire sum
`highestDualVars*`: values of the highest dual variable achieving max/max2/min

Tools

Common parameters: q =

Syndrome( k = , multiset = ) =

?

Affine( set = , × , + ) =

?

AffineAll( set = ) =

?

SyndromeAffineTransform( syndrome = , × , + ) =

?