An extension of the digital method
based on b-adic integers
Authors: Roswitha Hofer and Ísabel Pirsic
Speaker: Ísabel Pirsic
Affiliation: Johannes Kepler University Linz
Email: roswitha.hofer@jku.at, isabel.pirsic@jku.at
Funding: Austrian Science Fund, F5511-N26 (RH),
P27351-N26 (ÍP)

Discrepancy

A ‘measure for randomness’ for point sets
(as pertinent to specific applications)Distance from state of uniform distribution
Worst case error of numerical integrationof interval indicator functions
Many versions: different choices ofnorms, measures, weights, anchoring, wrapping ...


Here: star-discrepancy
Standard application:

Goal: low-discrepancy seq.sDN∗ (P) = supJ |AJ /N − λ(J)|RP| I f − N1 P f | ≤ V (f )DN∗ (P)
NDN∗ (P) ≈ O((log N)s )Good choice: point sets/seq.s obtained by digital method

Digital method (classical)
Simple example of LDS : van der Corput sequence —reflection of digit expansion at decimal point: 2341 7→ 0.1432
Digital method : map digit vectors to vectors over finite ring,
apply linear maps, map to [0, 1) by fractional
digit expansion
P>
n = i≥0 ni+1 b i
vn = (n̄1 , n̄2 , . . . ) ,wn,i = Ci · vn ,= (x̄n,i,1 , x̄n,i,2 , . . . )> 7→






C ∈ Mat (R), i=1,...,s
P−jxn,i = j>0 xn,i,j bi






Vectors, matrices, may be finite or infinite, but n always has afinite expansion (and mat-vec prod.s exist). OTOH, xn,i neednot, but is usually truncated to digit length of n.
Discrepancy then related to the ‘rank structure’ of thematrices : T (m), t -values defined by conditions of linearindependence of combinatorial subsets of row vectors of Ci

The quality parameters T (m), t
For integers m, t, m ≥ t ≥ 0 consider partitions
m − t = d1 + · · · + ds into nonnegative integers and for eachi = 1, . . . , s collect the initial di row vectors of Ci , truncatedto the first m coordinates, in a new matrix. If for eachpartition the rank of this matrix is m − t then T (m) := m − tis called the quality parameter at m of adigital (T (m), s)-sequence over R.
If limm (m − T (m)) = ∞ then the sequence is UD.
If T (m) ≤ t for all m then the sequence is an LDS withdiscrepancy boundDN∗ (P) ∈ O(b tlogs N).
N(Similar for a finite point set of size b mdigital (t, m, s)-net over R; (s − 1) in log-term)

b-adic integers Zb

A subring of the ring Qb , b need not be prime
Informally: Laurent series in b with +, ∗, . . . as in digitexpansion vectors of N. Then Zb = set of power series in b.
More formal: obtained by completion of Q with a(pseudo-)valuation (‘absolute value’), inducing a
non-archimedean metric. Then Zb = {a, |a|b ≤ 1}
|b 3 + b 5 |b = b −3 ,|b −4 + b + 1|b = b 4 ,√√3|6|24 = |18|24 = 1/ 3 24, |12|24 = 1/ 242 .
Usually: Qp , p prime, generally Qb ∼= Qp × · · · × Qp ,Examples:

1pi the distinct prime divisors of b.
Z ( Zb and Zb is indeed a subring as aboverUniform distribution of sequences in Z, Zb

UD mod m: asymp. frequency 1/m for all residue classes
UD mod Z: UD mod m, for all m > 1
UD mod Zb : k-digit truncations UD mod b k , for all k ≥ 0
Trivial case: (n)n≥0 is UD in Zb
Some sequences UD in Z (thus also in Zb ):(bαnc)n≥0 for irrational α(bf (n)c)n≥0 for f polynomial wheresome coefficient apart from the constant is irrational.
(bαnσ c)n≥0 for α arbitrary, σ positive, nonintegral.

Also: (an + c)n≥0 is UD in Zb if a ∈ Zb is a unit
(constant term is relative prime to b), c ∈ Zb arbitrary
Not UD in Zb (nor in Z): e.g., (n2 )n≥0

Extended Digital Method

Choose some sequence (sn )n≥0 in Zb(i.e., its b-adic expansion) as input
instead of (n)n≥0matrices need to have finite rows Extended Digital Method

Choose some sequence (sn )n≥0 in Zb(i.e., its b-adic expansion) as input
instead of (n)n≥0matrices need to have finite rows Note 1: finite-row-matrices are important in base-mixing
context

Extended Digital Method

Choose some sequence (sn )n≥0 in Zb(i.e., its b-adic expansion) as input
instead of (n)n≥0matrices need to have finite rows Note 1: finite-row-matrices are important in base-mixing
context
Note 2: true generalization, since, e.g., identity matrix and(αn2 + β)n≥0 give a sequence that can not be reproduced by
the classical method (nonlinear, nonfinite input, b-adic shift).

Extended Digital Method

Choose some sequence (sn )n≥0 in Zb(i.e., its b-adic expansion) as input
instead of (n)n≥0matrices need to have finite rows Note 1: finite-row-matrices are important in base-mixing
context
Note 2: true generalization, since, e.g., identity matrix and(αn2 + β)n≥0 give a sequence that can not be reproduced by
the classical method (nonlinear, nonfinite input, b-adic shift).
Theorem 1: If (fin.row) matrices Ci ∈ Mat∞ (Fq ) classicallygenerate a UD sequence and sn is UD in Zq then bothgenerate a UD sequence in the extended algorithm.

Extended Digital Method

Choose some sequence (sn )n≥0 in Zb(i.e., its b-adic expansion) as input
instead of (n)n≥0matrices need to have finite rows Note 1: finite-row-matrices are important in base-mixing
context
Note 2: true generalization, since, e.g., identity matrix and(αn2 + β)n≥0 give a sequence that can not be reproduced by
the classical method (nonlinear, nonfinite input, b-adic shift).
Theorem 1: If (fin.row) matrices Ci ∈ Mat∞ (Fq ) classicallygenerate a UD sequence and sn is UD in Zq then bothgenerate a UD sequence in the extended algorithm.
Converse does not hold: (n2 )n≥0 not UD, but there is a simple
matrix over F2 such that their combined sequence is UD

Extended Digital Method II

Theorem 2: Let C1 , . . . , Cs be ∞-matrices over Fq with row
length not exceeding their row index times s. If they generatea (0, s)-sequence then together with a sequence sn in Zq aUD sequence will be generated if and only if sn is UD in Zq .

Extended Digital Method II

Theorem 2: Let C1 , . . . , Cs be ∞-matrices over Fq with row
length not exceeding their row index times s. If they generatea (0, s)-sequence then together with a sequence sn in Zq aUD sequence will be generated if and only if sn is UD in Zq .
Remark: The case s = 1 and C1 = Id was proven byHellekallek and Niederreiter in a special case.

Extended Digital Method II

Theorem 2: Let C1 , . . . , Cs be ∞-matrices over Fq with row
length not exceeding their row index times s. If they generatea (0, s)-sequence then together with a sequence sn in Zq aUD sequence will be generated if and only if sn is UD in Zq .
Remark: The case s = 1 and C1 = Id was proven by
Hellekallek and Niederreiter in a special case.
Prop.2: Discrepancy estimate for (sn )n≥0 = (n + α)n≥0and generators of a (T (m), s)-sequence.
Cor.2: If additionally T (m) is bounded then alow-discrepancy sequence is generated.
Cor.3: If T (m) is bounded and gcd(v , q) = 1, α arbitrary,then sn = v1 n + α also generates a low-discrepancy sequence.

Numerical Experiments – Plots
Using Stirling matrices over F5 :Out[245]=

Numerical Experiments – Plots
Using Stirling matrices over F5 :Out[245]=

And three different input sequences:sn = nsn = h1, −1, 2, −2, . . . i
sn = 12 n − 14

Numerical Experiments – Plots
Using Stirling matrices over F5 :Out[245]=

And three different input sequences:sn = nsn = h1, −1, 2, −2, . . . i
sn = 12 n − 14... produces these point sets (500 pts):

Numerical Experiments – 1d-discrepancy
Using the identity matrix over F2

Numerical Experiments – 1d-discrepancy
Using the identity matrix over F2
And three different input sequences :black sn = ngray sn = h1, −1, 2, −2, . . . iblue sn = n − 1/(2 + 2−1 ) = n − 2/5

Numerical Experiments – 1d-discrepancy
Using the identity matrix over F2
And three different input sequences :black sn = ngray sn = h1, −1, 2, −2, . . . iblue sn = n − 1/(2 + 2−1 ) = n − 2/5... gives the following discrepancies (divided by log N/N):

Numerical Experiments – 2d-discrepancy
Using the Stirling matrices over F2

Numerical Experiments – 2d-discrepancy
Using the Stirling matrices over F2
And three different input sequences :black sn = ngray sn = −(n + 1)
blue sn = n − 1/(2 + 2−10 ) = n − 1024/2049

Numerical Experiments – 2d-discrepancy
Using the Stirling matrices over F2
And three different input sequences :black sn = ngray sn = −(n + 1)
blue sn = n − 1/(2 + 2−10 ) = n − 1024/2049... gives the following discrepancies (divided by log2 N/N):Open to research (and to reflect)
Determine const.s, e.g., for linear input seq.s more explicitly

Open to research (and to reflect)
Determine const.s, e.g., for linear input seq.s more explicitly
Composite b — Does anything unexpected happen ?

Open to research (and to reflect)
Determine const.s, e.g., for linear input seq.s more explicitly
Composite b — Does anything unexpected happen ?
Many more input sequences, esp.polynomials;
probably either not easy to investigate or not that good ...

Open to research (and to reflect)
Determine const.s, e.g., for linear input seq.s more explicitly
Composite b — Does anything unexpected happen ?
Many more input sequences, esp.polynomials;
probably either not easy to investigate or not that good ...
What about sequences of algebraic integers(i.e., algebraic integers in some Qp (α))?

Open to research (and to reflect)
Determine const.s, e.g., for linear input seq.s more explicitly
Composite b — Does anything unexpected happen ?
Many more input sequences, esp.polynomials;
probably either not easy to investigate or not that good ...
What about sequences of algebraic integers(i.e., algebraic integers in some Qp (α))?
Conceptually interesting: UD in Zb , or analogously, in Fb [[x]],can be spread out to UD in Fb [[x]]s by simple linear
transformation — what kind of matrices suffice(do we really need the full (t, s)-property)?

Open to research (and to reflect)
Determine const.s, e.g., for linear input seq.s more explicitly
Composite b — Does anything unexpected happen ?
Many more input sequences, esp.polynomials;
probably either not easy to investigate or not that good ...
What about sequences of algebraic integers(i.e., algebraic integers in some Qp (α))?
Conceptually interesting: UD in Zb , or analogously, in Fb [[x]],can be spread out to UD in Fb [[x]]s by simple linear
transformation — what kind of matrices suffice(do we really need the full (t, s)-property)?
Integrate a ‘discrepancy in integers’ into this frameweork

Open to research (and to reflect)
Determine const.s, e.g., for linear input seq.s more explicitly
Composite b — Does anything unexpected happen ?
Many more input sequences, esp.polynomials;
probably either not easy to investigate or not that good ...
What about sequences of algebraic integers(i.e., algebraic integers in some Qp (α))?
Conceptually interesting: UD in Zb , or analogously, in Fb [[x]],can be spread out to UD in Fb [[x]]s by simple linear
transformation — what kind of matrices suffice(do we really need the full (t, s)-property)?
Integrate a ‘discrepancy in integers’ into this frameweork
Silly questions : — Where does the powerful randomness ofmultivariate digital sequences ‘come from’ ? Zb ? FNb ? Or
which one rather, of the maps
vn : Zb 7→ FNb,(Ci )i : Fb [[x]] 7→ Fb [[x]]s ?

The End.

Thank youfor your kind attention !