Point arrangements on some combinatorial objects

概要

広島大学学位請求論文

Point arrangements on some
combinatorial objects.
(いくつかの組合せ論的対象上の点配置
について)

２０２２年
広島大学大学院理学研究科
数学専攻
梶浦 大起

目 次
１．主論文
Point arrangements on some combinatorial objects.
（いくつかの組合せ論的対象上の点配置について）
梶浦 大起
２．公表論文
(1) Characterization of matrices B such that (I, B, B 2) generates
a digital net with t-value zero.
Hiroki Kajiura, Makoto Matsumoto, Kosuke Suzuki.
Finite Fields and Their Applications, volume 52(2018),
289-300.
(2) Non-existence and Construction of Pre-difference Sets, and
Equi-Distributed Subsets in Association Schemes.
Hiroki Kajiura, Makoto Matsumoto, Takayuki Okuda.
Graphs and Combinatorics, volume 37(2021), 1531–1544.

主論文

Point arrangements on some combinatorial
objects
Hiroki Kajiura

Organization of this thesis
The subject of this thesis is to study and give characterizations of the existence and non-existence of “good point arrangements” for sets with mathematical structures. In Chapter 1, we study 3-dimensional digital nets (in
base 2), which are point arrangements on a cube [0, 1)3 . In Chapter 2, we
study pre-difference sets, which are point arrangements on a finite group.
We give an abstract for each chapter below:
Chapter 1. We study 3-dimensional digital nets over F2 generated by matrices (I, B, B 2 ) where I is the identity matrix and B is a square matrix.
We give a characterization of B for which the t-value of the digital net
is 0. As a corollary, we prove that such B satisfies B 3 = I.
Chapter 2. We gave a construction of a pre-difference set in G = N A with
A an abelian subgroup and N a subgroup satisfying N \ A = {e},
from a difference set in N ⇥ A. This gives a (16, 6, 2) pre-difference set
in D16 and a (27, 13, 6) pre-difference set in U T (3, 3), where no nontrivial difference sets exist. We also give a product construction of predifference sets similar to Kesava Menon construction, which provides
infinite series of pre-difference sets that are not difference sets. We
show some necessary conditions for the existence of a pre-difference set
in a group with index 2 subgroup. For the proofs, we use a rather
simple framework “relation partitions”, which is obtained by dropping
an axiom from association schemes. Most results are proved in that
frame work.

1

Contents
1 Characterization of matrices B such
a digital net with t-value zero
1.1 Introduction and main result . . .
1.2 Preliminaries . . . . . . . . . . . .
1.3 Proof of Theorem 1.1.1 . . . . . . .
1.4 Proofs of lemmas . . . . . . . . . .
1.4.1 Proof of Lemma 1.3.1 . . .
1.4.2 Proof of Lemma 1.3.2 . . .

that (I, B, B 2 ) generates
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

2 Non-existence and construction of pre-difference sets, and
equi-distributed subsets in association schemes
2.1 Pre-difference sets . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Relation partition, equi-distribution and difference set . . . . .
2.3 Construction of pre-difference sets from difference sets . . . .
2.4 Product for the case v = 4k 4 . . . . . . . . . . . . . . . .
2.5 Non-existence of pre-difference sets in some groups . . . . . .

2

3
3
6
9
10
10
10
13
13
15
19
20
23

Chapter 1
Characterization of matrices B
such that (I, B, B 2) generates a
digital net with t-value zero
1.1 Introduction and main result
Let F2 = {0, 1} be the field of two elements, m
1 be a positive integer,
and Fm⇥m
be
the
set
of
m
⇥
m
matrices
over
F
.
For
C1 , . . . , Cs 2 Fm⇥m
,
2
2
2
s
the digital net generated by (C1 , . . . , Cs ) is a point set in [0, 1) defined as
follows. For 0  l < 2m , we denote the 2-adic expansion of l by l = ◆0 + ◆1 2 +
· · · + ◆m 1 2m 1 with ◆0 , . . . , ◆m 1 2 F2 . We define y l,j 2 Fm
2 for 1  j  s as
y l,j := Cj (◆0 , . . . , ◆m 1 )> 2 Fm
2 .

Then we obtain the l-th point

xl := ( (y l,1 ), . . . , (y l,s ))
where

: Fm
2 ! [0, 1) is defined as
((y1 , . . . , ym )> ) :=

(1.1)

y1 y2
ym
+ 2 + ··· + m.
2
2
2

The digital net generated by (C1 , . . . , Cs ) is the point set {x0 , . . . , x2m 1 } ⇢
[0, 1)s . Digital nets are introduced by Niederreiter and have been widely
used to generate point sets in Quasi-Monte Carlo (QMC) theory, see [16] for
details.
3

A popular criterion of the uniformity of digital nets is the t-value. Let
m 1, 0  t  m, and s 1 be integers. A point set P = {x0 , . . . , x2m 1 } ⇢
[0, 1)s is called a (t, m, s)-net over F2 if, for all nonnegative
d1 , . . . , d s
Qs ⇥ integers
di
with d1 + · · · + ds = m t, the elementary intervals i=1 ai /2 , (ai + 1)/2di
contain exactly 2t points for all choices of 0  ai < 2di with ai 2 Z for
1  i  s. In this paper we study t-values of specific 3-dimensional digital
nets over F2 . Small value of t is preferable for QMC integration [16].
To state our main result, we introduce our notation. Let Im be the
m ⇥ m identity matrix. Let Jm be the m ⇥ m anti-diagonal matrix whose
anti-diagonal entries are all 1, and Pm be the m ⇥ m upper-triangular Pascal
matrix, i.e.,
0 0
1
1
. . . m0 1
0
1
0
0
0
1
B
.. C
✓✓
◆◆m
1
B
j 1
. C
B
C
.
1
C
Jm = @ . .
Pm =
=B
A,
B
.. C ,
..
i 1
@
i,j=1
.
. A
1
0
m 1
m 1

which are considered in modulo 2. If there is no confusion, we omit the
subscripts and simply write as I, J, and P . Let Lm (resp. Um ) be the
set of m ⇥ m lower- (resp. upper-) triangular matrices over F2 . Note that
Lm \Um = {I} holds. For matrices C1 , . . . , Cs 2 Fm⇥m
, t(C1 , . . . , Cs ) denotes
2
the t-value of the digital net generated by (C1 , . . . , Cs ).
Now we are ready to state our main result.
Theorem 1.1.1. Let m
are equivalent.

1 be an integer and B 2 Fm⇥m
. Then the following
2

(i) t(I, B, B 2 ) = 0.
(ii) There exists L 2 Lm such that B = LP JL 1 .

Moreover, if one of the above holds, then we have B 3 = I.
Note that for digital nets over F2 , t(C1 , . . . , Cs ) = 0 is achievable if and
only if s  3 (see [16, Corollary 4.21] or [8]). Thus, the above theorem shows
that this extreme s = 3 can be realized in the special form t(I, B, B 2 ).

4

Background. Our original motivation is to find a periodic sequence for
Markov Chain Quasi-Monte Carlo (MCQMC) method. Let us recall the
rough idea. Let x1 , x2 , . . . be a sequence of points in [0, 1). For an integer
s 1, we define
s
¯ (s)
x
i = (xi , xi+1 , . . . xi+s 1 ) 2 [0, 1) ,

(1.2)

where they are made up of overlapping consecutive s-tuples from the sequence. The sequence is said to be completely uniformly distributed (CUD)
s
¯ (s)
¯ (s)
if x
1.
1 ,x
2 , . . . is uniformly distributed in [0, 1) for all s
We do not explain on MCQMC method, but it is shown that CUD sequence can be used instead of uniformly i.i.d. uniform random numbers in
[0, 1). Markov Chain Monte Carlo (MCMC) with the driving sequence being
CUD is consistent to the original MCMC, see [2].
Constructions for CUD points given in [15] are not convenient to implement. Instead, it was suggested by Tribble [18] to use multiple congruential
generators and linear feedback shift registers. Chen et. al. [3] considered a
periodic sequence x1 , x2 , . . . with period p, the s-dimensional point set
(s)

Ss := {¯
xi = (xi , xi+1 , . . . xi+s 1 ) 2 [0, 1)s | i = 1, . . . , p}

(1.3)

whose cardinality is p as a multi set. It is expected to work well for MCQMC
if Ss is hyperuniform for every s. Assume that Ss [ {0} is a F2 -sub vector
space (this condition is necessary to compute t-value in a practical time)
of, say, dimension m. Here, each xi is assumed to be identified with an
element in Fm
2 through . Let V be this vector space Ss [ {0}. We further
require that S1 is a (0, m, 1)-net. Then, the projection to the first component
pr1 : V ! Fm
2 is linearly isomorphic. This implies that the second projection
pr2 : V ! Fm
2 is also isomorphic since the images of them are the same. Thus
pr2 pr1 1 is also isomorphic. This means that there is a fixed B 2 Fm⇥m
2
such that
xi+1 = Bxi
holds for i = 1, 2, . . .. Moreover, since we have assumed that Ss [ {0} is a
m-dimensional vector space, xi must take all non zero values once for 1  i 
p 1. This is equivalent that B is primitive (i.e., the multiplicative order of
B is 2m 1 and p = 2m 1). This type of pseudorandom number generator
is well studied, such as combined Tausworthe generators, see L’Ecuyer et. al.
[14]. Under our assumptions, we observe that the set
(s)

{¯
xi | 0  i < 2 m
5

1} [ {0}

is the digital net generated by (I, B, B 2 , . . . , B s 1 ), as a set.
Our original interest is to obtain such a maximal periodic B with small
t-value for wide s, to generate a pseudo-CUD sequence. For example, t = 0
might be possible for s = 2, which is the theoretical bound stated above
(below Theorem 1.1.1). However, an exhaustive search for matrices B with
t(I, B, B 2 ) = 0 for m  5 resulted non-primitive B. Actually, we obtained
a negative result Theorem 1.1.1: For s = 3 and m
3, the digital net
generated by (I, B, B 2 ) is a (0, m, 3)-net only if B 3 = I. Thus there is no
B 2 Fm⇥m
satisfying our assumptions for m 3. Hence we conclude that our
2
construction of F2 -linear generator with maximal period is not optimal with
respect to the t-value for s = 3. We need to consider some looser condition,
such as considered in [3].

1.2 Preliminaries
We first recall results for t-value of digital nets. It is known that t-value
of digital nets is related to the linear independence of column vectors of
generating matrices.
Lemma 1.2.1 ([6, Theorem 4.52]). Let C1 , . . . , Cs 2 Fm⇥m
and denote by
2
j
ci the j-th row of Ci . Assume that, for all choices of nonnegative integers
d1 , . . . , ds with d1 + · · · + ds = m t, m t vectors {cji | 1  j  di } are linear
independent. Then the digital net generated by (C1 , . . . , Cs ) is a (t, m, s)-net
over F2 .
Lemma 1.2.2. Let C1 , . . . , Cs 2 Fm⇥m
and L1 , . . . , Ls 2 Lm . Let G 2 Fm⇥m
2
2
be non-singular. Then we have t(C1 , · · · , Cs ) = t(L1 C1 G, · · · , Ls Cs G).

Proof. ...