Boolean polynomial expression of the discrete average on the space of rhythms

Fumio HAZAMA
Tokyo Denki University
Hatoyama, Hiki-Gun, Saitama JAPAN
e-mail address:[email protected]
Phone number: (81)49-296-5267

Abstract

An infinite family of Boolean polynomials which correspond to the discrete average maps, defined in [2], is constructed. Each member $Bav_{N}^{0}$ of the family is found to be balanced. A recursive formula, which computes $Bav_{N+1}^{0}$ from $Bav_{N}^{0}$ , is provided.

$\mathbf{Keywords}$ : Boolean polynomial, space of rhythms, discrete average, Boolean average, balanced polynomial
MSC 2010: 05E18, 06E30, 37P25.

0 Introduction

The main purpose of this paper is to construct a Boolean counterpart of the discrete average map $Rav$ , investigated in [2], and to study its algebraic and combinatorial properties. The map $Rav$ is defined on a space $\mathbf{R}_{N}^{n}$ of rhythms with $N$ beats and with $n$ onsets, and it is shown that an arbitrary rhythm in $\mathbf{R}_{N}^{n}$ can be made smooth by a finite number of iterations of $Rav$ . An observation which motivates our study in the present paper is that a certain quotient space $\overline{\mathbf{R}}_{N}^{n}$ of $\mathbf{R}_{N}=\cup_{n=0}^{N}\mathbf{R}_{N}^{n}$ is found to be naturally isomorphic to the Boolean space $\mathbf{B}_{N}=\mathbf{F}_{2}^{N}$ , and that the discrete average descends to a self map on $\overline{\mathbf{R}}_{N}^{n}$ . It follows that there should be a Boolean counterpart $Bav:\mathbf{B}_{N}\rightarrow\mathbf{B}_{N}$ , which might shed light on the true nature of $Rav$ from the Boolean viewpoint. We do not assume the reader’s acquaintance with any theory of music. We will encounter some unexpected algebraic phenomena which might be entitled to be investigated independently of its rhythm-theoretical origin.
As a self map on $\mathbf{B}_{N}$ , the Boolean average $Bav$ consists of $N$ Boolean functions. We show, however, that only one of them, called $Bav_{N}^{0}$ , determines the other $N-1$ functions completely. Furthermore we derive a formula which expresses $Bav_{N}^{0}$ as a sum of a simple-looking products (Theorem 5.2), and obtain a recurrence formula which computes $Bav_{N}^{0}$ from $Bav_{N-1}^{0}$ (Theorem 5.3). As a consequence, we see that the Boolean polynomial $Bav_{N}^{0}$ is balanced. According to [4, Chapter 3.3], “Boolean functions in cryptographic applications almost always need to be balanced, … .” Our polynomials $Bav_{N}^{0}$ for $N\geq 3$ provide us unexpectedly with an infinite family of balanced ones.
The plan of this paper is as follows. In Section one, we recall the definition of the space $\mathbf{R}_{N}^{n}$ of rhythms and of the discrete average $Rav$ on $\mathbf{R}_{N}^{n}$ . The space $\mathbf{R}_{N}^{n}$ is defined to be a subset of the self-product $\mathbf{Z}_{N}^{n}$ of $\mathbf{Z}_{N}=\{0,1,\cdots,N-1\}$ equipped with the addition and subtraction operations inherited from those on the abelian group $\mathbf{Z}/N\mathbf{Z}$ . Thus rhythms are originally inhabitants of the “modulo- $N$ -world.” Since our investigation in this article is based on the fact that $Rav$ preserves the space $\mathbf{R}_{N}^{n}$ , we give a simplified proof of this fact here. In Section two, we construct a bridge from this modulo- $N$ -world to the Boolean world by introducing a certain equivalence relation on $\mathbf{R}_{N}$ , which is compatible with the map $Rav$ . The quotient space $\overline{\mathbf{R}}_{N}^{n}$ by this relation is found to be naturally isomorphic to the Boolean space $\mathbf{B}_{N}$ , and hence we obtain Boolean counterpart $Bav_{N}$ , called Boolean average, on $\mathbf{B}_{N}$ . Section three is devoted to deduce several functorial properties of the Boolean average, which enable us to show that only one of the coordinate $Bav_{N}^{0}$ of the self map $Bav_{N}$ is enough to determine the other coordinates. In Section four we recall a standard way to translate a given propositional function to a Boolean polynomial. By this method one can express the $N$ coordinates of $Bav$ as Boolean polynomials. However several examples of the polynomial expressions of $Bav_{N}^{0}$ for small $N$ are listed in Table 4.3, they do not give any clue for our attempt to express the polynomials in a unified way. This obstacle leads us to change the basic set of indices $\mathbf{Z}_{N}$ of Boolean vectors to the set $\mathbf{Z}_{N,\pm}$ of the least absolute remainders modulo $N$ . Thanks to the transition to $\mathbf{Z}_{N,\pm}$ we obtain in Section five a simple formula which expresses the polynomial $Bav_{N}^{0}$ . In order to formulate the result we introduce the notion of a ”parental pair of zero”, and that of an ”ancestor of zero” for which $Bav_{N}^{0}$ takes value 1. By determining the structure of the set of ancestors of zero, we find an explicit form of $Bav_{N}^{0}$ as well as some recurrence formulas. Furthermore we derive from the structure of the set of the ancestors of zero that $Bav_{N}^{0}$ is always balanced for any $N\geq 3$ .

1 The discrete average on the space of rhythms $\mathbf{R}_{N}^{n}$

In this section we recall some definitions in our previous paper [2], and reformulate them in more geometric language. Throughout the present article we fix an integer $N$ which is assumed to be greater than or equal to 3.

1.1 $\mathbf{Z}_{N}$ -interval and $S^{1}$ -interval

Let $\mathbf{Z}_{N}=\{0,1,\cdots,N-1\}$ . We denote by $\langle n\rangle_{N}$ the least nonnegative remainder of an integer $n$ divided by $N$ . We define the addition ” $+_{N}$ ” and the difference ” $-_{N}$ ” on $\mathbf{Z}_{N}$ by the rules

	$\displaystyle a+_{N}b$	$\displaystyle=$	$\displaystyle\langle a+b\rangle_{N},$
	$\displaystyle a-_{N}b$	$\displaystyle=$	$\displaystyle\langle a-b\rangle_{N},$

for any $a,b\in\mathbf{Z}_{N}$ . For any pair $a,b\in\mathbf{Z}_{N}$ , we define the $\mathbf{Z}_{N}$ -interval $[a,b]_{\mathbf{Z}_{N}}$ by

\displaystyle[a,b]_{\mathbf{Z}_{N}}=\left\{\begin{array}[]{ll}\{a,a+1,\cdots,b\},&\mbox{if $a\leq b$},\\ \{a,a+1,\cdots,N-1,0,1,\cdots,b\},&\mbox{if $a>b$},\end{array}\right.

and define half-closed intervals by

	$\displaystyle[a,b)_{\mathbf{Z}_{N}}$	$\displaystyle=$	$\displaystyle[a,b]_{\mathbf{Z}_{N}}\setminus\{b\},$
	$\displaystyle(a,b]_{\mathbf{Z}_{N}}$	$\displaystyle=$	$\displaystyle[a,b]_{\mathbf{Z}_{N}}\setminus\{a\}.$

Therefore the number $|[a,b)_{\mathbf{Z}_{N}}|$ of the elements in $[a,b)_{\mathbf{Z}_{N}}$ is given by

\displaystyle|[a,b)_{\mathbf{Z}_{N}}|=b-_{N}a.

(1.2)

We call the number $b-_{N}a$ the $\mathbf{Z}_{N}$ -distance from $a$ to $b$ , and denote it by $d_{\mathbf{Z}_{N}}(a,b)$ . Note that, when $a\neq b$ , the distance satisfies the equality

\displaystyle d_{\mathbf{Z}_{N}}(a,b)=N-d_{\mathbf{Z}_{N}}(b,a),

hence it is not necessarily symmetric. These two notions, $\mathbf{Z}_{N}$ -interval and $\mathbf{Z}_{N}$ distance, are translated into geometric ones through a character on the additive group $\mathbf{R}$ as follows. Let $S^{1}=\{z\in\mathbf{C}:|z|=1\}\subset\mathbf{C}$ be the unit circle in the complex plane, and let $\chi_{N}:\mathbf{R}\rightarrow\mathbf{C}^{*}=\mathbf{C}\setminus\{0\}$ denote the additive character defined by $\chi_{N}(t)=\exp(2\pi it/n)$ for any $t\in\mathbf{R}$ . Note that $\chi_{N}(\mathbf{R})=S^{1}$ and that $\chi_{N}(\mathbf{Z}_{N})=\mu_{N}$ , where $\mu_{N}$ denotes the group of the $N$ -th roots of unity. For any pair $(z,w)\in S^{1}\times S^{1}$ , we define the $S^{1}$ -interval $[z,w]_{S^{1}}\subset S^{1}$ to be the counterclockwise closed circular arc from $z$ to $w$ , and put

	$\displaystyle[z,w)_{S^{1}}$	$\displaystyle=$	$\displaystyle[z,w]_{S^{1}}\setminus\{w\},$
	$\displaystyle(z,w]_{S^{1}}$	$\displaystyle=$	$\displaystyle[z,w]_{S^{1}}\setminus\{z\}.$

Let $d_{S^{1}}(z,w)$ denote the length of the arc $[z,w]_{S^{1}}$ . We call $d_{S^{1}}(z,w)$ the $S^{1}$ -distance from $z$ to $w$ . Note that we have

\displaystyle d_{S^{1}}(z,w)=2\pi-d_{S^{1}}(w,z),

for any distinct pair of elements $z,w\in S^{1}$ . The $\mathbf{Z}_{N}$ -distance and the $S^{1}$ -distance are related by the equation

\displaystyle d_{S^{1}}(\chi_{N}(a),\chi_{N}(b))=\frac{2\pi}{N}d_{\mathbf{Z}_{N}}(a,b),

(1.3)

for any $(a,b)\in\mathbf{Z}_{N}\times\mathbf{Z}_{N}$ . For any pair $(z,w)\in\mu_{N}\times\mu_{N}$ , we define the $\mu_{N}$ -interval $[z,w]_{\mu_{N}}$ by

\displaystyle[z,w]_{\mu_{N}}

\displaystyle=

\displaystyle[z,w]_{S^{1}}\cap\mu_{N},

and let

	$\displaystyle[z,w)_{\mu_{N}}$	$\displaystyle=$	$\displaystyle[z,w]_{\mu_{N}}\setminus\{w\},$
	$\displaystyle(z,w]_{\mu_{N}}$	$\displaystyle=$	$\displaystyle[z,w]_{\mu_{N}}\setminus\{z\}.$

Note that, for any $(a,b)\in\mathbf{Z}_{N}\times\mathbf{Z}_{N}$ , the map $\chi_{N}$ defines a bijection from the $\mathbf{Z}_{N}$ -interval $[a,b]_{\mathbf{Z}_{N}}$ to the $\mu_{N}$ -interval $[\chi_{N}(a),\chi_{N}(b)]_{\mu_{N}}$ .

1.2 $\mathbf{Z}_{N}$ -average and $\mu_{N}$ -average

First we define a map $av_{\mathbf{Z}_{N}}:\mathbf{Z}_{N}\times\mathbf{Z}_{N}\rightarrow\mathbf{Z}_{N}$ by the rule

\displaystyle av_{\mathbf{Z}_{N}}(a,b)=a+_{N}\left\lfloor\frac{b-_{N}a}{2}\right\rfloor

(1.4)

for any $(a,b)\in\mathbf{Z}_{N}\times\mathbf{Z}_{N}$ . However we use the notation “ $rav$ ” in [2] to express this map $av_{\mathbf{Z}_{N}}$ , we rename it in this paper in order to contrast it with a corresponding average on $\mu_{N}$ . The latter is defined as follows. For any $(z,w)\in S^{1}\times S^{1}$ , we denote the midpoint of the circular arc $[z,w]_{S^{1}}$ by $av_{S^{1}}(z,w)$ , and call it $S^{1}$ -average of $z$ and $w$ . Furthermore a kind of rounding-off operator $\lfloor\cdot\rfloor_{\mu_{N}}$ on $S^{1}$ is introduced as follows. Note that we have the equality

\displaystyle S^{1}=\bigsqcup_{k=0}^{N-1}[\zeta_{N}^{k},\zeta_{N}^{k+1})_{S^{1}},

where $\zeta_{N}=\chi_{N}(1)$ . Hence for any $z\in S^{1}$ , there exists a unique $k\in\mathbf{Z}_{N}$ such that $z\in[\zeta_{N}^{k},\zeta_{N}^{k+1})_{S^{1}}$ . We put $\lfloor z\rfloor_{\mu_{N}}=\zeta_{N}^{k}$ employing this $k$ . The $\mu_{N}$ -average $av_{\mu_{N}}(z,w)$ of $(z,w)\in\mu_{N}\times\mu_{N}$ is define by

\displaystyle av_{\mu_{N}}(z,w)=\lfloor av_{S^{1}}(z,w)\rfloor_{\mu_{N}}.

The following proposition shows that the $\mathbf{Z}_{N}$ -average corresponds to the $\mu_{N}$ -average through the bijection $\chi_{N}|_{\mathbf{Z}_{N}}$ .

Proposition 1.1.

For any $(a,b)\in\mathbf{Z}_{N}\times\mathbf{Z}_{N}$ , we have

\displaystyle\chi_{N}(av_{\mathbf{Z}_{N}}(a,b))=av_{\mu_{N}}(\chi_{N}(a),\chi_{N}(b)),

(1.5)

namely, the diagram

\displaystyle\begin{CD}\mathbf{Z}_{N}\times\mathbf{Z}_{N}@>{\chi_{N}\times\chi_{N}}>{}>\mu_{N}\times\mu_{N}\\ @V{av_{\mathbf{Z}_{N}}}V{}V@V{av_{\mu_{N}}}V{}V\\ \mathbf{Z}_{N}@>{\chi_{N}}>{}>\mu_{N}\\ \end{CD}

commutes.

Proof.

For the proof, we employ the following lemma.

Lemma 1.1.

For any $(a,b)\in\mathbf{Z}_{N}\times\mathbf{Z}_{N}$ , we have

\displaystyle av_{\mathbf{Z}_{N}}(a,b)=\left\{\begin{array}[]{ll}\left\lfloor\frac{a+b}{2}\right\rfloor,&\mbox{if }a\leq b,\\ \langle\left\lfloor\frac{a+b+N}{2}\right\rfloor\rangle_{N},&\mbox{if }a>b.\\ \end{array}\right.

(1.8)

Proof of Lemma 1.1. Suppose that $a\leq b$ . Then we have

$\displaystyle\chi_{N}(av_{\mathbf{Z}_{N}}(a,b))$	$\displaystyle=$	$\displaystyle\chi_{N}(a+_{N}\left\lfloor\frac{b-_{N}a}{2}\right\rfloor)$
	$\displaystyle=$	$\displaystyle\chi_{N}(a)\chi_{N}(\left\lfloor\frac{b-a}{2}\right\rfloor)$
	$\displaystyle=$	$\displaystyle\chi_{N}(a+\left\lfloor\frac{b-a}{2}\right\rfloor)$
	$\displaystyle=$	$\displaystyle\chi_{N}(\left\lfloor\frac{a+b}{2}\right\rfloor).$

Since $0\leq a\leq b\leq N-1$ , we have $0\leq\left\lfloor\frac{a+b}{2}\right\rfloor\leq N-1$ , and hence the assertion (1.5) holds by the bijectivity of $\chi_{N}|_{\mathbf{Z}_{N}}$ . When $a>b$ , we have $b-_{N}a=b-a+N$ . Hence we have

$\displaystyle\chi_{N}(av_{\mathbf{Z}_{N}}(a,b))$	$\displaystyle=$	$\displaystyle\chi_{N}(a+_{N}\left\lfloor\frac{b-_{N}a}{2}\right\rfloor)$
	$\displaystyle=$	$\displaystyle\chi_{N}(a)\chi_{N}(\left\lfloor\frac{b-a+N}{2}\right\rfloor)$
	$\displaystyle=$	$\displaystyle\chi_{N}(a+\left\lfloor\frac{b-a+N}{2}\right\rfloor)$
	$\displaystyle=$	$\displaystyle\chi_{N}(\left\lfloor\frac{a+b+N}{2}\right\rfloor).$

This time we need to take the remainder modulo $N$ of $\left\lfloor\frac{a+b+N}{2}\right\rfloor$ , which need not be smaller than $N$ . This finishes the proof of Lemma 1.1.
With the help of this lemma, we can prove Proposition 1.1. When $a\leq b$ , by the definition of $av_{S^{1}}$ , we see that $av_{S^{1}}(\chi_{N}(a),\chi_{N}(b))=\chi_{N}(\frac{a+b}{2})$ , since the usual average $(a+b)/2$ is the midpoint of the interval $[a,b]\subset\mathbf{R}$ . Therefore $av_{\mu_{N}}(\chi_{N}(a),\chi_{N}(b))=\chi_{N}(\lfloor\frac{a+b}{2}\rfloor)$ , which is equal to $\chi_{N}(av_{\mathbf{Z}_{N}}(a,b))$ by Lemma 1.1. The case when $a>b$ can be treated similarly also by Lemma 1.1. ∎

As a consequence, we can prove the following.

Proposition 1.2.

(1) For any $(z,w)\in\mu_{N}\times\mu_{N}$ , we have

\displaystyle av_{\mu_{N}}(z,w)\in[z,w]_{\mu_{N}}.

(2) For any $(a,b)\in\mathbf{Z}_{N}\times\mathbf{Z}_{N}$ , we have

\displaystyle av_{\mathbf{Z}_{N}}(a,b)\in[a,b]_{\mathbf{Z}_{N}}.

Proof.

(1) The midpoint $av_{S^{1}}(z,w)$ belongs to $[z,w]_{S^{1}}$ by definition, and hence $av_{\mu_{N}}(z,w)=\lfloor av_{S^{1}}(z,w)\rfloor_{\mu_{N}}\in[z,w]_{\mu_{N}}$ , since the rounding-off operator cannot go beyond $z\in\mu_{N}$ .
(2) Let $c=av_{\mathbf{Z}_{N}}(a,b)$ . Then if follows from (1.4) that

\displaystyle\chi_{N}(c)=av_{\mu_{N}}(\chi_{N}(a),\chi_{N}(b)),

and hence

\displaystyle\chi_{N}(c)\in[\chi_{N}(a),\chi_{N}(b)]_{\mu_{N}}

(1.9)

by the above (1). Since $\chi_{N}$ is a bijection from $[a,b]_{\mathbf{Z}_{N}}$ onto $[\chi_{N}(a),\chi_{N}(b)]_{\mu_{N}}$ , the statement (1.6) implies that $c=av_{\mathbf{Z}_{N}}(a,b)\in[a,b]_{\mathbf{Z}_{N}}$ . This completes the proof. ∎

Noting that the midpoint of $[z,w]_{S^{1}}$ coincides with $w$ only when $z=w$ , we obtain the following.

Corollary 1.1.

(1) For any pair $(z,w)$ of distinct elements of $\mu_{N}$ , we have

\displaystyle av_{\mu_{N}}(z,w)\in[z,w)_{\mu_{N}}.

(2) For any pair $(a,b)$ of distinct elements of $\mathbf{Z}_{N}$ , we have

\displaystyle av_{\mathbf{Z}_{N}}(a,b)\in[a,b)_{\mathbf{Z}_{N}}.

1.3 The space of rhythms and the discrete average transformation

In this subsection, we recall the definition of the space of rhythms given in [2], and reformulate it by employing the $S^{1}$ -average and the $\mu_{N}$ -average.

Definition 1.1.

For any positive integer $n$ with $2\leq n\leq N$ , an $n$ -tuple $\mathbf{a}=(a_{0},\cdots,a_{n-1})\in\mathbf{Z}_{N}^{n}$ is said to be a rhythm modulo $N$ with $n$ onsets, if $a_{i}\neq a_{j}$ for $i\neq j$ , and the following condition holds:

\displaystyle\sum_{i=0}^{n-1}(a_{i+1}-_{N}a_{i})=N.

(1.10)

(Here the summation on the left hand side means the usual addition of integers, and $a_{n}$ is set to be $a_{0}$ .) We denote by $\mathbf{R}_{N}^{n}$ the set of rhythms modulo $N$ with $n$ onsets.

This is the original definition given in [2] of the space of rhythms. Note that the condition (1.7) is equivalent to the equality

\displaystyle\mathbf{Z}_{N}=\bigsqcup_{i=0}^{n-1}[a_{i},a_{i+_{n}1})_{\mathbf{Z}_{N}}.

(1.11)

Applying the map $\chi_{N}$ to the both sides of (1.8) we obtain another equivalent condition

\displaystyle S^{1}=\bigsqcup_{i=0}^{n-1}[\chi_{N}(a_{i}),\chi_{N}(a_{i+_{n}1}))_{S^{1}},

(1.12)

which says that the ordered set $(\chi_{N}(a_{0}),\cdots,\chi_{N}(a_{n-1}))$ constitutes a simple convex $n$ -gon inscribed in $S^{1}$ . The condition (1.9) clarifies the meaning of the algebraic condition (1.7) in more geometric terms, and will be employed frequently afterwards.
In order to make our transition to the Boolean world smooth, we need, however, to define the space $\mathbf{R}_{N}^{1}$ of rhythms with 1 onset as well as $\mathbf{R}_{N}^{0}$ . The following definition fills the gap:

Definition 1.2.

Any singleton $(a)$ of $a\in\mathbf{Z}_{N}$ is regarded as a rhythm with 1 onset. The empty set $\phi$ is considered to be the unique rhythm with 0 onset. Accordingly we define

	$\displaystyle\mathbf{R}_{N}^{1}$	$\displaystyle=$	$\displaystyle\{(a);a\in\mathbf{Z}_{N}\},$
	$\displaystyle\mathbf{R}_{N}^{0}$	$\displaystyle=$	$\displaystyle\{\phi\}.$

Furthermore we define the total space of rhythms $\mathbf{R}_{N}$ with $N$ beats by

\displaystyle\mathbf{R}_{N}=\bigcup_{n=0}^{N}\mathbf{R}_{N}^{n}.

The discrete average transformation on $\mathbf{R}_{N}$ , which is the central topic in [2], is defined as follows.

Definition 1.3.

For a rhythm $\mathbf{a}=(a_{0},\cdots,a_{n-1})\in\mathbf{R}_{N}^{n}$ with $2\leq n\leq N$ , we define its discrete average transformation $Rav(\mathbf{a})$ by

\displaystyle Rav(\mathbf{a})=(av_{\mathbf{Z}_{N}}(a_{0},a_{1}),av_{\mathbf{Z}_{N}}(a_{1},a_{2}),\cdots,av_{\mathbf{Z}_{N}}(a_{n-1},a_{0})).

(1.13)

Since we have enlarged the space of rhythms in Definition 1.2, we need to define discrete average on $\mathbf{R}_{N}^{1}$ and $\mathbf{R}_{N}^{0}$ too. This is accomplished simply as follows:

Definition 1.4.

For any $(a)\in\mathbf{R}_{N}^{1}$ , we define

\displaystyle Rav((a))=(a),

(1.14)

and on $\mathbf{R}_{N}^{0}$ we put

\displaystyle Rav(\phi)=\phi.

(1.15)

Remark 1.1.

It follows from the definition that $av_{\mathbf{Z}_{N}}(a,a)=0$ holds for any $a\in\mathbf{Z}_{N}$ . Hence our definition (1.11) is natural.

The main purpose of this subsection is to show that the discrete average transformation $Rav$ maps $\mathbf{R}_{N}$ into itself. This fact is proved in [2] through an algebraic argument. We, however, give below a simpler and more geometric proof.

Proposition 1.3.

For any $\mathbf{a}\in\mathbf{R}_{N}^{n}$ , we have $Rav(\mathbf{a})\in\mathbf{R}_{N}^{n}$ .

Proof.

We may assume that $n\geq 2$ , since the assertion follows directly from Definition 1.4 when $n=0$ or $n=1$ . Let $Rav(\mathbf{a})=\mathbf{b}=(b_{0},b_{1},\cdots,b_{n-1})$ . It follows from the assumption that we have

\displaystyle S^{1}=\bigsqcup_{i=0}^{n-1}[\chi_{N}(a_{i}),\chi_{N}(a_{i+_{n}1}))_{S^{1}}.

Furthermore it follows from Proposition 1.1 and Corollary 1.1 that

\displaystyle\chi_{N}(b_{i})\in[\chi_{N}(a_{i}),\chi_{N}(a_{i+_{n}1}))_{\mu_{N}}.

Hence we have

\displaystyle S^{1}=\bigsqcup_{i=0}^{n-1}[\chi_{N}(b_{i}),\chi_{N}(b_{i+_{n}1}))_{S^{1}}.

Therefore the $n$ -tuple $\mathbf{b}$ satisfies the condition (1.9), and hence $\mathbf{b}\in\mathbf{R}_{N}^{n}$ . This completes the proof. ∎

2 From modulo- $N$ -world to the Boolean world

The purpose of this section is to construct a Boolean counterpart of the discrete average transformation $Rav$ on $\mathbf{R}_{N}$ . We accomplish this by introducing two intermediate spaces $\overline{\mathbf{R}}_{N}$ and $\mathbf{I}_{N}$ , which lie between $\mathbf{R}_{N}$ and our destination, the Boolean space $\mathbf{B}_{N}=\mathbf{F}_{2}^{N}$ . We define a certain average map on each of the new spaces, and build three bridges $\pi,s,ItoB$ between each pair of the four spaces, which make the following diagram commutative.

\displaystyle\begin{CD}\mathbf{R}_{N}@>{\pi}>{}>\overline{\mathbf{R}}_{N}@>{s}>{}>\mathbf{I}_{N}@>{ItoB}>{}>\mathbf{B}_{N}\\ @V{Rav}V{}V@V{\overline{R}av}V{}V@V{Iav}V{}V@V{Bav}V{}V\\ \mathbf{R}_{N}@>{\pi}>{}>\overline{\mathbf{R}}_{N}@>{s}>{}>\mathbf{I}_{N}@>{ItoB}>{}>\mathbf{B}_{N}\\ \end{CD}

2.1 Quotient map $\mathbf{R}_{N}^{n}\rightarrow\overline{\mathbf{R}}_{N}^{n}$ and its section

A self map ” $rot$ ” on $\mathbf{R}_{N}^{n}$ is introduced in [2]. Let us recall the definition and supply it with additional versions for the case $n=0,1$ :

Definition 2.1.

For any $\mathbf{a}=(a_{0},a_{1},\cdots,a_{n-1})\in\mathbf{R}_{N}^{n}$ with $2\leq n\leq N$ , let

\displaystyle rot(\mathbf{a})=(a_{n-1},a_{0},\cdots,a_{n-2}).

(2.1)

When $n=0,1$ , it is defined to be the identity, namely,

	$\displaystyle rot((a_{0}))$	$\displaystyle=$	$\displaystyle(a_{0})\mbox{ for any }(a_{0})\in\mathbf{R}_{N}^{1},$		(2.2)
	$\displaystyle rot(\phi)$	$\displaystyle=$	$\displaystyle\phi.$		(2.3)

Note that $rot(\mathbf{a})\in\mathbf{R}_{N}^{n}$ for any $\mathbf{a}\in\mathbf{R}_{N}^{n}$ . We define an equivalence relation on $\mathbf{R}_{N}^{n}$ employing this map as follows:

Definition 2.2.

For any pair $\mathbf{a},\mathbf{b}\in\mathbf{R}_{N}^{n}$ , they are said to be equivalent if there exists an integer $k$ such that

\displaystyle rot^{k}(\mathbf{a})=\mathbf{b}.

Since the map $rot$ is bijective, this defines an equivalence relation on $\mathbf{R}_{N}^{n}$ , which we denote by ” $\sim_{rot}$ ”.

Definition 2.3.

We denote by $\overline{\mathbf{R}}_{N}^{n}$ the quotient of $\mathbf{R}_{N}^{n}$ by the equivalence relation $\sim_{rot}$ :

\displaystyle\overline{\mathbf{R}}_{N}^{n}=\mathbf{R}_{N}^{n}/\sim_{rot},

and by $\pi:\mathbf{R}_{N}^{n}\rightarrow\overline{\mathbf{R}}_{N}^{n}$ the natural projection.

Remark 2.1.

Our definition of ” $rot$ ” here is actually the inverse of the one used in $[2]$ . The reason why we adopt the inverse is that it makes several formulas in this paper look more natural. The equivalence relation ” $\sim_{rot}$ ”, however, is actually defined through the action of the group $\mathbf{Z}_{n}$ , generated by $rot$ , hence the quotient space $\overline{\mathbf{R}}_{N}^{n}$ is exactly the same as the one defined in $[$ loc.cit. $]$ .

Remark 2.2.

When $n=0,1$ , the space $\overline{\mathbf{R}}_{N}^{n}$ is nothing other than $\mathbf{R}_{N}^{n}$ , since $rot$ is the identity on $\mathbf{R}_{N}^{1}$ or on $\mathbf{R}_{N}^{0}$ .

It follows from Definition 1.3, 1.4, and 2.1 that the two self maps $rot$ and $Rav$ on $\mathbf{R}_{N}^{n}$ commute with each other for any $n\geq 0$ :

\displaystyle rot\circ Rav=Rav\circ rot,

namely, we have the following commutative diagram:

\displaystyle\begin{CD}\mathbf{R}_{N}^{n}@>{rot}>{}>\mathbf{R}_{N}^{n}\\ @V{Rav}V{}V@V{Rav}V{}V\\ \mathbf{R}_{N}^{n}@>{rot}>{}>\mathbf{R}_{N}^{n}\\ \end{CD}

Therefore the map $Rav$ descends to a self map $\overline{R}av$ on $\overline{\mathbf{R}}_{N}^{n}$ , namely, the equality

\displaystyle\pi\circ Rav=\overline{R}av\circ\pi.

(2.4)

holds. Hence we have the following commutative diagram:

\displaystyle\begin{CD}\mathbf{R}_{N}^{n}@>{\pi}>{}>\overline{\mathbf{R}}_{N}^{n}\\ @V{Rav}V{}V@V{\overline{R}av}V{}V\\ \mathbf{R}_{N}^{n}@>{\pi}>{}>\overline{\mathbf{R}}_{N}^{n}\\ \end{CD}

2.2 Construction of a section of $\pi$

The purpose of this subsection is to construct a section of the quotient map $\pi:\mathbf{R}_{N}^{n}\rightarrow\overline{\mathbf{R}}_{N}^{n}$ . Here the notion of jumping number, introduced in [2], plays a crucial role.

Definition 2.4.

When $n\geq 2$ , for any $\mathbf{a}=(a_{0},a_{1},\cdots,a_{n-1})\in\mathbf{R}_{N}^{n}$ , there is a unique number $j\in\mathbf{Z}_{n}$ such that $a_{j-_{n}1}>a_{j}$ and that $a_{k-_{n}1}<a_{k}$ holds for every other $k\in\mathbf{Z}_{n}\setminus\{j\}$ . The number $j$ is called the jumping number of $\mathbf{a}$ . When $n=1$ , the jumping number of an arbitrary element $(a_{0})$ of $\mathbf{R}_{N}^{1}$ is defined to be $0$ , In any case it is denoted by $j(\mathbf{a})$ .

Remark 2.3.

Our definition of the jumping number increases the corresponding number defined in $[2]$ by one. One of the main reasons why we adopt this version is that we want every element in the basic set $\mathbf{I}_{N}^{n}$ , defined in Definition 2.5 later, of increasing sequences to acquire the jumping number $0$ . Since we derive several results in this paper by choosing from $\mathbf{I}_{N}^{n}$ a representative of the class in $\overline{\mathbf{R}}_{N}^{n}$ , this convention makes our description simpler.

We can characterize the jumping number in geometric and intuitive terms by employing the half-closed intervals.

Proposition 2.1.

Assume that $n\geq 2$ . For any $\mathbf{a}=(a_{0},a_{1},\cdots,a_{n-1})\in\mathbf{R}_{N}^{n}$ , the jumping number $j(\mathbf{a})$ is equal to the unique number $i\in\mathbf{Z}_{n}$ such that the half-open interval $(\chi_{N}(a_{i-_{n}1}),\chi_{N}(a_{i})]_{S^{1}}$ contains $1\in S^{1}$ .

Proof.

Replacing the left-closed and right-open intervals in the condition (1.9) by the left-open and right-closed intervals, we obtain an equivalent condition

\displaystyle S^{1}=\bigsqcup_{i=0}^{n-1}(\chi_{N}(a_{i-_{n}1}),\chi_{N}(a_{i})]_{S^{1}}.

Hence there exists a unique member $i\in\mathbf{Z}_{n}$ such that

\displaystyle 1\in(\chi_{N}(a_{i-_{n}1}),\chi_{N}(a_{i})]_{S^{1}}.

This condition is equivalent to the condition that

\displaystyle 0\in(a_{i-_{n}1},a_{i}]_{\mathbf{Z}_{N}},

which holds if and only if $j(\mathbf{a})=i$ . This completes the proof. ∎

By the very definition of the jumping number, we have the following:

Proposition 2.2.

For any $\mathbf{a}\in\mathbf{R}_{N}^{n}$ , we have

\displaystyle j(rot(\mathbf{a}))=j(\mathbf{a})+_{n}1.

Proof.

Let $\mathbf{a}=(a_{0},\cdots,a_{n-1})$ and $rot(\mathbf{a})=\mathbf{b}=(b_{0},\cdots,b_{n-1})$ so that

\displaystyle b_{i}=a_{i-_{n}1}

(2.5)

holds for any $i\in\mathbf{Z}_{n}$ . If we put $j=j(\mathbf{a})$ , then we have

\displaystyle 0\leq a_{j}<a_{j+_{n}1}<\cdots<a_{j-_{n}1}\leq N-1.

This series of inequalities is equivalent to

\displaystyle 0\leq b_{j+_{n}1}<b_{j+_{n}2}<\cdots<b_{j}\leq N-1

by (2.5). Hence $j(\mathbf{b})=j+_{n}1$ . This completes the proof. ∎

As a direct consequence, we obtain the following:

Corollary 2.1.

For any $x\in\overline{\mathbf{R}}_{N}^{n}$ , the set of jumping numbers of the elements in the fiber $\pi^{-1}(x)$ coincides with the whole $\mathbf{Z}_{n}$ .

As a result, we can choose from each fiber of $\pi$ a unique rhythm with its jumping number equal to zero. For this reason, we introduce the following:

Definition 2.5.

We denote by $\mathbf{I}_{N}^{n}$ the subset of $\mathbf{R}_{N}^{n}$ which consists of every element $(a_{0},\cdots,a_{n-1})\in\mathbf{R}_{N}^{n}$ such that

\displaystyle 0\leq a_{0}<\cdots<a_{n-1}\leq N-1,

(2.6)

namely, we put

\displaystyle\mathbf{I}_{N}^{n}=\{\mathbf{a}\in\mathbf{R}_{N}^{n};j(\mathbf{a})=0\}.

Remark 2.4.

The condition (2.6) says that the sequence $(a_{0},\cdots,a_{n-1})$ is increasing. We adopt its initial as the name of the space.

Proposition 2.2 enables one to find the unique element in $\pi^{-1}(x)\cap\mathbf{I}_{N}^{n}$ algorhythmically:

Proposition 2.3.

For any $\mathbf{a}\in\mathbf{R}_{N}^{n}$ , let

\displaystyle pr_{\mathbf{I}}(\mathbf{a})=rot^{n-_{n}j(\mathbf{a})}(\mathbf{a}).

(2.7)

Then it defines a contraction map $pr_{\mathbf{I}}:\mathbf{R}_{N}^{n}\rightarrow\mathbf{I}_{N}^{n}$ such that

\displaystyle pr_{\mathbf{I}}\circ\iota_{\mathbf{I}}=id_{\mathbf{I}_{N}^{n}},

(2.8)

where $\iota_{\mathbf{I}}:\mathbf{I}_{N}^{n}\rightarrow\mathbf{R}_{N}^{n}$ denotes the natural inclusion map.

Proof.

It follows form Proposition 2.2 and (2.7) that

\displaystyle j(pr_{\mathbf{I}}(\mathbf{a}))=j(\mathbf{a})+_{n}(n-_{n}j(\mathbf{a}))=0.

Hence $pr_{\mathbf{I}}(\mathbf{a})\in\mathbf{I}_{N}^{n}$ . Furthermore, if $\mathbf{a}\in\mathbf{I}_{N}^{n}$ , then $j(\mathbf{a})=0$ , and hence $pr_{\mathbf{I}}(\mathbf{a})=\mathbf{a}$ . This shows that the equality (2.8) holds true. This completes the proof. ∎

Thus we obtain a section of the quotient map $\pi$ :

Proposition 2.4.

For any $\mathbf{a}\in\mathbf{R}_{N}^{n}$ , let

\displaystyle s(\pi(\mathbf{a}))=pr_{\mathbf{I}}(\mathbf{a}).

Then $s$ defines a section of the quotient map $\pi:\mathbf{R}_{N}^{n}\rightarrow\overline{\mathbf{R}}_{N}^{n}$ , and its image coincides with the set $\mathbf{I}_{N}^{n}$ . In particular $\mathbf{I}_{N}^{n}$ and $\overline{\mathbf{R}}_{N}^{n}$ are in one-to-one correspondence.

Remark 2.5.

When $n=0,1$ , we define $s:\overline{\mathbf{R}}_{N}^{n}\rightarrow\mathbf{R}_{N}^{n}$ to be the identity map. (See Remark 2.2.)

2.3 From $\overline{\mathbf{R}}_{N}^{n}$ to Boolean world via $\mathbf{I}_{N}^{n}$

In a standard way, the set $\mathbf{I}_{N}^{n}$ is connected directly to the Boolean world. For later use we introduce some notations and make the connection clear:

Definition 2.6.

Let $\mathbf{B}_{N}$ denote the $N$ -dimensional vector space $\mathbf{F}_{2}^{N}$ over the prime field $\mathbf{F}_{2}=\{0,1\}$ . For any vector $\mathbf{v}\in\mathbf{B}_{N}$ , we denote by $supp(\mathbf{v})$ the set of indices of the non-zero entries of $\mathbf{v}$ ,

\displaystyle supp(\mathbf{v})=\{i\in\mathbf{Z}_{N};v_{i}=1\}\subset\mathbf{Z}_{N},

and let

\displaystyle\mathbf{B}_{N}^{n}=\{\mathbf{v}\in\mathbf{B}_{N};|supp(\mathbf{v})|=n\}

for any $n$ with $0\leq n\leq N$ , so that

\displaystyle\mathbf{B}_{N}=\bigcup_{n=0}^{N}\mathbf{B}_{N}^{n}.

First we relate every element in $\mathbf{R}_{N}^{n}$ to $\mathbf{B}_{N}^{n}$ by taking its characteristic function:

Definition 2.7.

With any $\mathbf{a}\in\mathbf{R}_{N}^{n}$ , we associate a vector

\displaystyle RtoB(\mathbf{a})=(v_{0},\cdots,v_{N-1})\in\mathbf{B}_{N}

by the rule

\displaystyle v_{i}=\left\{\begin{array}[]{ll}1,&\mbox{ if $i\in\mathbf{a}$,}\\ 0,&\mbox{ if $i\not\in\mathbf{a}$.}\\ \end{array}\right.

This gives us the map

\displaystyle RtoB:\mathbf{R}_{N}^{n}\rightarrow\mathbf{B}_{N}^{n}.

Note that the following simple but important equality

\displaystyle RtoB\circ rot=RtoB.

(2.10)

holds, since the map $rot$ does not change the contents of any rhythms. It follows from (2.9) that

\displaystyle RtoB\circ pr_{\mathbf{I}}=RtoB,

(2.11)

since $pr_{\mathbf{I}}$ is a power of $rot$ by the definition (2.7).
Next, based on the map $RtoB$ , we relate $\mathbf{I}_{N}^{n}$ with $\mathbf{B}_{N}^{n}$ :

Definition 2.8.

For any $n$ -element subset $S$ of $\mathbf{Z}_{N}$ , by arranging its elements in increasing order

\displaystyle 0\leq s_{0}<s_{1}<\cdots<s_{n-1}\leq N-1,

we define

\displaystyle ord(S)=(s_{0},\cdots,s_{n-1}).

We put

	$\displaystyle ItoB$	$\displaystyle=$	$\displaystyle RtoB\circ\iota_{\mathbf{I}}:\mathbf{I}_{N}^{n}\rightarrow\mathbf{B}_{N}^{n},$		(2.12)
	$\displaystyle BtoI$	$\displaystyle=$	$\displaystyle ord\circ supp:\mathbf{B}_{N}^{n}\rightarrow\mathbf{I}_{N}^{n}.$		(2.13)

Since one can check that

	$\displaystyle ItoB\circ BtoI$	$\displaystyle=$	$\displaystyle id_{\mathbf{B}_{N}^{n}},$		(2.14)
	$\displaystyle BtoI\circ ItoB$	$\displaystyle=$	$\displaystyle id_{\mathbf{I}_{N}^{n}},$		(2.15)

$\mathbf{I}_{N}^{n}$ and $\mathbf{B}_{N}^{n}$ are in one-to-one correspondence.
Finally, we relate the quotient space $\overline{\mathbf{R}}_{N}^{n}$ with $\mathbf{B}_{N}^{n}$ .

Proposition 2.5.

Let $\overline{R}toB:\overline{\mathbf{R}}_{N}^{n}\rightarrow\mathbf{B}_{N}^{n}$ be the map defined by

\displaystyle\overline{R}toB=ItoB\circ s,

(2.16)

and let $Bto\overline{R}:\mathbf{B}_{N}^{n}\rightarrow\overline{\mathbf{R}}_{N}^{n}$ be the map defined by

\displaystyle Bto\overline{R}=\pi\circ BtoI.

(2.17)

These maps are inverse to each other:

	$\displaystyle Bto\overline{R}\circ\overline{R}toB$	$\displaystyle=$	$\displaystyle id_{\overline{\mathbf{R}}_{N}^{n}},$		(2.18)
	$\displaystyle\overline{R}toB\circ Bto\overline{R}$	$\displaystyle=$	$\displaystyle id_{\mathbf{B}_{N}^{n}}.$		(2.19)

In particular, the sets $\overline{\mathbf{R}}_{N}^{n}$ and $\mathbf{B}_{N}^{n}$ are in one-to-one correspondence.

Proof.

First we compute $Bto\overline{R}\circ\overline{R}toB$ as follows:

$\displaystyle Bto\overline{R}\circ\overline{R}toB$	$\displaystyle=$	$\displaystyle(\pi\circ BtoI)\circ(ItoB\circ s)$
	$\displaystyle=$	$\displaystyle\pi\circ s\hskip 42.67912pt\mbox{ (by (2.14))}$
	$\displaystyle=$	$\displaystyle id_{\overline{\mathbf{R}}_{N}^{n}},$

hence we have (2.17). For the validity of (2.18), we note that, by Proposition 2.4, the composite map $s\circ\pi:\mathbf{R}_{N}^{n}\rightarrow\mathbf{R}_{N}^{n}$ becomes the identity when restricted to the subset $\mathbf{I}_{N}^{n}$ . Hence

$\displaystyle\overline{R}toB\circ Bto\overline{R}$	$\displaystyle=$	$\displaystyle(ItoB\circ s)\circ(\pi\circ BtoI)$
	$\displaystyle=$	$\displaystyle ItoB\circ BtoI$
	$\displaystyle=$	$\displaystyle id_{\mathbf{B}_{N}^{n}},$

the last equality being a consequence of (2.13). This completes the proof. ∎

The two maps $RtoB$ and $\overline{R}toB$ are related in a natural way:

Proposition 2.6.

We have

\displaystyle\overline{R}toB\circ\pi=RtoB.

Proof.

Combining several defining equations, we compute as follows:

$\displaystyle\overline{R}toB\circ\pi$	$\displaystyle=$	$\displaystyle ItoB\circ s\circ\pi\hskip 28.45274pt(\mbox{by }(2.15))$
	$\displaystyle=$	$\displaystyle ItoB\circ pr_{\mathbf{I}}\hskip 34.1433pt(\mbox{by Proposition }2.4)$
	$\displaystyle=$	$\displaystyle RtoB\circ\iota_{\mathbf{I}}\circ pr_{\mathbf{I}}\hskip 17.07164pt(\mbox{by }(2.11))$
	$\displaystyle=$	$\displaystyle RtoB\circ pr_{\mathbf{I}}$
	$\displaystyle=$	$\displaystyle RtoB.\hskip 56.9055pt(\mbox{by }(2.10))$

This finishes the proof. ∎

2.4 Counterpart of $Rav$ on $\mathbf{I}_{N}^{n}$

The discrete average map $Rav:\mathbf{R}_{N}^{n}\rightarrow\mathbf{R}_{N}^{n}$ , to our regret, does not keep the subspace $\mathbf{I}_{N}^{n}\subset\mathbf{R}_{N}^{n}$ invariant. For example, for $\mathbf{a}=(2,3,7)\in\mathbf{I}_{8}^{3}$ , its discrete average is

\displaystyle Rav(2,3,7)=(2,5,0),

which does not belong to $\mathbf{I}_{8}^{3}$ . In order to overcome this inconvenience and to define a self map $Iav$ on $\mathbf{I}_{N}^{n}$ , we introduce the following notion:

Definition 2.9.

A rhythm $\mathbf{a}=(a_{0},\cdots,a_{n-1})\in\mathbf{I}_{N}^{n}$ is said to be proper, if

\displaystyle N-a_{n-1}>a_{0}.

(2.20)

If it is not proper, it is called improper.

The following proposition relates the properness of an increasing rhythm with its behavior under the discrete average map.

Proposition 2.7.

(1) For an increasing rhythm $\mathbf{a}=(a_{0},\cdots,a_{n-1})\in\mathbf{I}_{N}^{n}$ , it is proper if and only if $Rav(\mathbf{a})\in\mathbf{I}_{N}^{n}$ .
(2) If $\mathbf{a}=(a_{0},\cdots,a_{n-1})\in\mathbf{I}_{N}^{n}$ is improper, then $rot(Rav(\mathbf{a}))\in\mathbf{I}_{N}^{n}$ .

Proof.

(1) Let $Rav(\mathbf{a})=\mathbf{b}=(b_{0},b_{1},\cdots,b_{n-1})$ . By Corollary 1.1, (2), we have a series of inequalities

\displaystyle 0\leq a_{0}\leq b_{0}<a_{1}\leq b_{1}<a_{2}\leq\cdots<a_{n-2}\leq b_{n-2}<a_{n-1}\leq N-1.

(2.21)

Therefore only the behavior of $b_{n-1}=av_{\mathbf{Z}_{N}}(a_{n-1},a_{0})$ determines whether $\mathbf{b}$ belongs to $\mathbf{I}_{N}^{n}$ or not. Note that the condition (2.19) is expressed as

\displaystyle d_{\mathbf{Z}_{N}}(a_{n-1},0)>d_{\mathbf{Z}_{N}}(0,a_{0}).

Since the two distances $d_{\mathbf{Z}_{N}}$ and $d_{S^{1}}$ are in proportion through the map $\chi_{N}$ by (1.2), this inequality is equivalent to

\displaystyle d_{S^{1}}(\chi_{N}(a_{n-1}),1)>d_{S^{1}}(1,\chi_{N}(a_{0})).

This condition holds if and only if the midpoint $av_{S^{1}}(\chi_{N}(a_{n-1}),\chi_{N}(a_{0}))$ lies on the $S^{1}$ -interval $[\chi_{N}(a_{n-1}),1)_{S^{1}}$ . Moreover the last condition is equivalent to $av_{\mu_{N}}(\chi_{N}(a_{n-1}),\chi_{N}(a_{0}))\in[\chi_{N}(a_{n-1}),1)_{S^{1}}$ . It follows from Proposition 1.1 that this is equivalent to the condition that $av_{\mathbf{Z}_{N}}(a_{n-1},a_{0})\in[a_{n-1},0)_{\mathbf{Z}_{N}}$ , which together with (2.20) says that $Rav(\mathbf{a})\in\mathbf{I}_{N}^{n}$ .
(2) If $\mathbf{a}=(a_{0},\cdots,a_{n-1})\in\mathbf{I}_{N}^{n}$ is improper, then it follows from the proof for the point (1) that

\displaystyle 0\leq b_{n-1}<a_{0}\leq b_{0}<a_{1}\leq b_{1}<a_{2}\leq\cdots\leq b_{n-2}<a_{n-1}\leq N-1.

(2.22)

Therefore $rot(\mathbf{b})=(b_{n-1},b_{0},b_{1},\cdots,b_{n-2})\in\mathbf{I}_{N}^{n}$ . This completes the proof. ∎

The following lemma is a rephrasing of Proposition 2.7.

Corollary 2.2.

For any increasing rhythm $\mathbf{a}\in\mathbf{I}_{N}^{n}$ , we introduce the number $p(\mathbf{a})\in\{0,1\}$ by the rule

\displaystyle p(\mathbf{a})=\left\{\begin{array}[]{ll}0,&\mbox{ if }\mathbf{a}\mbox{ is proper,}\\ 1,&\mbox{ if }\mathbf{a}\mbox{ is improper.}\\ \end{array}\right.

Then we have

\displaystyle rot^{p(\mathbf{a})}(Rav(\mathbf{a}))\in\mathbf{I}_{N}^{n}.

Now we can define $\mathbf{I}$ -version of the discrete average transformation as follows:

Definition 2.10.

For any $\mathbf{a}\in\mathbf{I}_{N}^{n}$ , let

\displaystyle Iav(\mathbf{a})=rot^{p(\mathbf{a})}(Rav(\mathbf{a})).

It follows from Corollary 2.2 that $Iav$ defines a self map on $\mathbf{I}_{N}^{n}$ :

\displaystyle Iav:\mathbf{I}_{N}^{n}\rightarrow\mathbf{I}_{N}^{n}.

The following proposition shows that $Iav$ is compatible with $\overline{R}av$ :

Proposition 2.8.

We have the following equality

\displaystyle\pi|_{\mathbf{I}_{N}^{n}}\circ Iav=\overline{R}av\circ\pi|_{\mathbf{I}_{N}^{n}},

(2.24)

namely, the diagram

\displaystyle\begin{CD}\mathbf{I}_{N}^{n}@>{\pi|_{\mathbf{I}_{N}^{n}}}>{}>\overline{\mathbf{R}}_{N}^{n}\\ @V{Iav}V{}V@V{\overline{R}av}V{}V\\ \mathbf{I}_{N}^{n}@>{\pi|_{\mathbf{I}_{N}^{n}}}>{}>\overline{\mathbf{R}}_{N}^{n}\\ \end{CD}

commutes.

Proof.

Let $\mathbf{a}$ be an arbitrary element of $\mathbf{I}_{N}^{n}$ . When $\mathbf{a}$ is proper, it follows from Definition 2.10 and Corollary 2.2 that $Iav(\mathbf{a})=Rav(\mathbf{a})$ . Hence the equality (2.22) follows from (2.4). When $\mathbf{a}$ is improper, it follows from Definition 2.10 that $Iav(\mathbf{a})=rot(Rav(\mathbf{a}))$ . Hence we have

$\displaystyle(\pi\|_{\mathbf{I}_{N}^{n}}\circ Iav)(\mathbf{a})$	$\displaystyle=$	$\displaystyle\pi\|_{\mathbf{I}_{N}^{n}}(rot(Rav(\mathbf{a})))$
	$\displaystyle=$	$\displaystyle\pi(rot(Rav(\mathbf{a})))$
	$\displaystyle=$	$\displaystyle\pi(Rav(\mathbf{a}))\hskip 14.22636pt(\mbox{by the definition of the quotient map }\pi)$
	$\displaystyle=$	$\displaystyle(\overline{R}av\circ\pi)(\mathbf{a})\hskip 8.53581pt(\mbox{by }(2.4))$
	$\displaystyle=$	$\displaystyle(\overline{R}av\circ\pi\|_{\mathbf{I}_{N}^{n}})(\mathbf{a}).$

This completes the proof. ∎

Since $\pi|_{\mathbf{I}_{N}^{n}}:\mathbf{I}_{N}^{n}\rightarrow\overline{\mathbf{R}}_{N}^{n}$ and $s:\overline{\mathbf{R}}_{N}^{n}\rightarrow\mathbf{I}_{N}^{n}$ are inverse to each other, this proposition implies the following:

Corollary 2.3.

We have the following equality

\displaystyle Iav\circ s=s\circ\overline{R}av,

(2.25)

namely, the diagram

\displaystyle\begin{CD}\mathbf{I}_{N}^{n}@<{}<{s}<\overline{\mathbf{R}}_{N}^{n}\\ @V{Iav}V{}V@V{\overline{R}av}V{}V\\ \mathbf{I}_{N}^{n}@<{}<{s}<\overline{\mathbf{R}}_{N}^{n}\\ \end{CD}

commutes.

This corollary in turn implies the following:

Corollary 2.4.

We have the following equality

\displaystyle Iav\circ pr_{\mathbf{I}}=pr_{\mathbf{I}}\circ Rav,

(2.26)

namely, the diagram

\displaystyle\begin{CD}\mathbf{I}_{N}^{n}@<{}<{pr_{\mathbf{I}}}<\mathbf{R}_{N}^{n}\\ @V{Iav}V{}V@V{Rav}V{}V\\ \mathbf{I}_{N}^{n}@<{}<{pr_{\mathbf{I}}}<\mathbf{R}_{N}^{n}\\ \end{CD}

commutes.

Proof.

Since $pr_{\mathbf{I}}=s\circ\pi$ , we can compute as follows:

$\displaystyle Iav\circ pr_{\mathbf{I}}$	$\displaystyle=$	$\displaystyle Iav\circ s\circ\pi$
	$\displaystyle=$	$\displaystyle s\circ\overline{R}av\circ\pi\hskip 14.22636pt(\mbox{by }(2.23))$
	$\displaystyle=$	$\displaystyle s\circ\pi\circ Rav\hskip 14.22636pt(\mbox{by }(2.4))$
	$\displaystyle=$	$\displaystyle pr_{\mathbf{I}}\circ Rav\hskip 14.22636pt(\mbox{by }(2.4)).$

This completes the proof. ∎

2.5 Counterpart of $Rav$ on $\mathbf{B}_{N}^{n}$

We transport the discrete average on $\overline{\mathbf{R}}_{N}^{n}$ to the corresponding map on $\mathbf{B}_{N}^{n}$ :

Definition 2.11.

The Boolean average $Bav:\mathbf{B}_{N}^{n}\rightarrow\mathbf{B}_{N}^{n}$ is defined by

\displaystyle Bav=\overline{R}toB\circ\overline{R}av\circ Bto\overline{R},

(2.27)

which makes the following diagram commute:

\displaystyle\begin{CD}\overline{\mathbf{R}}_{N}^{n}@>{\overline{R}toB}>{}>\mathbf{B}_{N}^{n}\\ @V{\overline{R}av}V{}V@V{Bav}V{}V\\ \overline{\mathbf{R}}_{N}^{n}@>{\overline{R}toB}>{}>\mathbf{B}_{N}^{n}\\ \end{CD}

Namely the equality

\displaystyle Bav\circ\overline{R}toB=\overline{R}toB\circ\overline{R}av

(2.28)

holds.

The following lemma relates $Bav$ with $Iav$ :

Lemma 2.1.

\displaystyle Bav=ItoB\circ Iav\circ BtoI.

(2.29)

Proof.

This is proved by inserting the defining equations (2.15), (2.16) into (2.25) as follows:

$\displaystyle Bav$	$\displaystyle=$	$\displaystyle\overline{R}toB\circ\overline{R}av\circ Bto\overline{R}$
	$\displaystyle=$	$\displaystyle ItoB\circ s\circ\overline{R}av\circ\pi\circ BtoI\hskip 28.45274pt(\mbox{by }(2.15),(2.16))$
	$\displaystyle=$	$\displaystyle ItoB\circ s\circ\pi\circ Iav\circ BtoI\hskip 28.45274pt(\mbox{by }(2.22))$
	$\displaystyle=$	$\displaystyle ItoB\circ Iav\circ BtoI.\hskip 56.9055pt(\mbox{by Proposition }2.4)$

This finishes the proof. ∎

Since $ItoB$ is the inverse of $BtoI$ , we have the following:

Proposition 2.9.

We have the equality

\displaystyle Bav\circ ItoB=ItoB\circ Iav,

(2.30)

namely, the diagram

\displaystyle\begin{CD}\mathbf{I}_{N}^{n}@>{ItoB}>{}>\mathbf{B}_{N}^{n}\\ @V{Iav}V{}V@V{Bav}V{}V\\ \mathbf{I}_{N}^{n}@>{ItoB}>{}>\mathbf{B}_{N}^{n}\\ \end{CD}

commutes.

Thus we have accomplised the purpose of this section, namely our construction of three maps $\overline{R}av,Iav,Bav$ , each of which corresponds to the discrete average map $Rav$ on $\mathbf{R}_{N}$ .
The following example indicates how we can compute $Iav$ and $Bav$ :
Example 2.1. Let $N=8$ and $n=3$ . For the vector $\mathbf{v}=(0,0,1,1,0,0,0,1)\in\mathbf{B}_{8}^{3}$ , we can compute $Bav(\mathbf{v})$ as follows:

$\displaystyle Bav(\mathbf{v})$	$\displaystyle=$	$\displaystyle(ItoB\circ Iav\circ BtoI)(0,0,1,1,0,0,0,1)\hskip 14.22636pt(\mbox{by Lemma 2.1)}$
	$\displaystyle=$	$\displaystyle(ItoB(Iav(2,3,7))\hskip 99.58464pt(\mbox{by (2.12)})$
	$\displaystyle=$	$\displaystyle ItoB(rot(Rav(2,3,7)))\hskip 42.67912pt(\mbox{since }(2,3,7)\mbox{ is improper})$
	$\displaystyle=$	$\displaystyle ItoB(rot(2,5,0))$
	$\displaystyle=$	$\displaystyle ItoB(0,2,5)$
	$\displaystyle=$	$\displaystyle(1,0,1,0,0,1,0,0),$

the last quality coming from (2.11) and Definition 2.7.

3 Cyclicity of the components of the Boolean average

Our main theme in this paper is to investigate the properties of the Boolean average $Bav$ . As a map from $\mathbf{F}_{2}^{N}$ to itself, $Bav$ has $N$ components each of which is a Boolean function on $\mathbf{F}_{2}^{N}$ . In this section we show that only one of these $N$ Boolean functions determines the shapes of the other $N-1$ functions. For this purpose we need to check the functorialities of several maps.

3.1 Boolean counterpart of the translation map $tr$ on $\mathbf{R}_{N}^{n}$

In [2], we introduce a self map $tr:\mathbf{R}_{N}^{n}\rightarrow\mathbf{R}_{N}^{n}$ when $n\geq 2$ , which is defined by

\displaystyle tr(a_{0},\cdots,a_{n-1})=(a_{0}+_{N}1,\cdots,a_{n-1}+_{N}1)

for any $(a_{0},\cdots,a_{n-1})\in\mathbf{R}_{N}^{n}$ . When $n=1$ or $n=0$ , we supply this with the following natural ones:

	$\displaystyle tr(a_{0})$	$\displaystyle=$	$\displaystyle(a_{0}+_{N}1),$
	$\displaystyle tr(\phi)$	$\displaystyle=$	$\displaystyle\phi.$

Since this map $tr$ commutes with the map $rot$ for any $n\geq 0$ , It descends to a self map on $\overline{\mathbf{R}}_{N}^{n}$ , which we denote by $\overline{R}tr$ :

\displaystyle\overline{R}tr:\overline{\mathbf{R}}_{N}^{n}\rightarrow\overline{\mathbf{R}}_{N}^{n}.

Therefore we have

\displaystyle\overline{R}tr\circ\pi

\displaystyle=

\displaystyle\pi\circ tr,

(3.1)

namely, we have the following commutative diagram:

\displaystyle\begin{CD}\mathbf{R}_{N}^{n}@>{\pi}>{}>\overline{\mathbf{R}}_{N}^{n}\\ @V{tr}V{}V@V{\overline{R}tr}V{}V\\ \mathbf{R}_{N}^{n}@>{\pi}>{}>\overline{\mathbf{R}}_{N}^{n}\\ \end{CD}

Next we show that the map $tr$ commutes with $Rav$ :

Proposition 3.1.

The two self maps $tr$ and $Rav$ on $\mathbf{R}_{N}^{n}$ commute with each other:

\displaystyle tr\circ Rav=Rav\circ tr,

namely, we have the following commutative diagram:

\displaystyle\begin{CD}\mathbf{R}_{N}^{n}@>{tr}>{}>\mathbf{R}_{N}^{n}\\ @V{Rav}V{}V@V{Rav}V{}V\\ \mathbf{R}_{N}^{n}@>{tr}>{}>\mathbf{R}_{N}^{n}\\ \end{CD}

Proof.

It follows from the definition of the $\mathbf{Z}_{N}$ -average that

\displaystyle av_{\mathbf{Z}_{N}}(a+_{N}1,b+_{N}1)

\displaystyle=

\displaystyle av_{\mathbf{Z}_{N}}(a,b)+_{N}1.

(3.2)

Therefore for any $\mathbf{a}=(a_{0},\cdots,a_{n-1})\in\mathbf{R}_{N}^{n}$ , we have

$\displaystyle(Rav\circ tr)(\mathbf{a})$	$\displaystyle=$	$\displaystyle Rav(tr(a_{0},\cdots,a_{n-1}))$
	$\displaystyle=$	$\displaystyle Rav(a_{0}+_{N}1,\cdots,a_{n-1}+_{N}1)$
	$\displaystyle=$	$\displaystyle(av_{\mathbf{Z}_{N}}(a_{0}+_{N}1,a_{1}+_{N}1),\cdots,av_{\mathbf{Z}_{N}}(a_{n-1}+_{N}1,a_{0}+_{N}1))$
	$\displaystyle=$	$\displaystyle(av_{\mathbf{Z}_{N}}(a_{0},a_{1})+_{N}1,\cdots,av_{\mathbf{Z}_{N}}(a_{n-1},a_{0})+_{N}1)\hskip 14.22636pt(\mbox{by }(3.2))$
	$\displaystyle=$	$\displaystyle(tr\circ Rav)(\mathbf{a}).$

This completes the proof. ∎

Since we have seen that both maps $tr$ and $Rav$ on $\mathbf{R}_{N}^{n}$ descend to the corresponding maps on $\overline{\mathbf{R}}_{N}^{n}$ , this proposition implies the following:

Corollary 3.1.

For the two self maps $\overline{R}av$ and $\overline{R}tr$ , the equality

\displaystyle\overline{R}av\circ\overline{R}tr=\overline{R}tr\circ\overline{R}av,

(3.3)

holds, namely, the following diagram commutes:

\displaystyle\begin{CD}\overline{\mathbf{R}}_{N}^{n}@>{\overline{R}tr}>{}>\overline{\mathbf{R}}_{N}^{n}\\ @V{\overline{R}av}V{}V@V{\overline{R}av}V{}V\\ \overline{\mathbf{R}}_{N}^{n}@>{\overline{R}tr}>{}>\overline{\mathbf{R}}_{N}^{n}\\ \end{CD}

Next we define a Boolean counterpart $Btr$ of $tr$ :

Definition 3.1.

Let $Btr:\mathbf{B}_{N}\rightarrow\mathbf{B}_{N}$ denote the map defined by

\displaystyle Btr(v_{0},v_{1},v_{2},\cdots,v_{N-1})=(v_{N-1},v_{0},v_{1},\cdots,v_{N-2})

for any $\mathbf{v}=(v_{0},v_{1},v_{2},\cdots,v_{N-1})\in\mathbf{B}_{N}$ .

The following proposition shows the compatibility of $Btr$ and $tr$ :

Proposition 3.2.

We have the equality of maps:

\displaystyle Btr\circ RtoB=RtoB\circ tr,

(3.4)

namely, the following diagram commutes:

\displaystyle\begin{CD}\mathbf{R}_{N}^{n}@>{RtoB}>{}>\mathbf{B}_{N}^{n}\\ @V{tr}V{}V@V{Btr}V{}V\\ \mathbf{R}_{N}^{n}@>{RtoB}>{}>\mathbf{B}_{N}^{n}\\ \end{CD}

Proof.

For any $\mathbf{a}=(a_{0},a_{1},\cdots,a_{n-1})\in\mathbf{R}_{N}^{n}$ , Definition 2.7 implies that

\displaystyle RtoB(\mathbf{a})=\mathbf{v}=(v_{0},v_{1},\cdots,v_{N-1})\in\mathbf{B}_{N}^{n},

where

\displaystyle v_{i}=\left\{\begin{array}[]{ll}1,&\mbox{ if $i\in\mathbf{a}$},\\ 0,&\mbox{ if $i\not\in\mathbf{a}$},\\ \end{array}\right.

Therefore the left hand side of (3.4) maps $\mathbf{a}$ to

	$\displaystyle Btr(RtoB(\mathbf{a}))$	$\displaystyle=$	$\displaystyle Btr(v_{0},v_{1},\cdots,v_{N-1})$
		$\displaystyle=$	$\displaystyle(v_{N-1},v_{0},\cdots,v_{N-2}).$

Let $w_{i}=v_{i-_{N}1}$ for any $i\in\mathbf{Z}_{N}$ . Then we have

\displaystyle\mathbf{w}=(w_{0},w_{1},\cdots,w_{N-1})=(v_{N-1},v_{0},\cdots,v_{N-2}),

namely we have

\displaystyle\mathbf{w}=Btr(RtoB(\mathbf{a})).

Notice that we have the following series of equivalences:

$\displaystyle w_{i}=1$	$\displaystyle\Leftrightarrow$	$\displaystyle v_{i-_{N}1}=1$
	$\displaystyle\Leftrightarrow$	$\displaystyle i-_{N}1\in\mathbf{a}$
	$\displaystyle\Leftrightarrow$	$\displaystyle i\in tr(\mathbf{a}).$

It follows that

\displaystyle\mathbf{w}=RtoB(tr(\mathbf{a})).

Hence we have

\displaystyle Btr\circ RtoB=RtoB\circ tr,

This completes the proof. ∎

As an immediate consequence, we have the following:

Corollary 3.2.

The equality of composite maps

\displaystyle Btr\circ\overline{R}toB=\overline{R}toB\circ\overline{R}tr

(3.6)

holds, namely, the following diagram commutes:

\displaystyle\begin{CD}\overline{\mathbf{R}}_{N}^{n}@>{\overline{R}toB}>{}>\mathbf{B}_{N}^{n}\\ @V{\overline{R}tr}V{}V@V{Btr}V{}V\\ \overline{\mathbf{R}}_{N}^{n}@>{\overline{R}toB}>{}>\mathbf{B}_{N}^{n}\\ \end{CD}

Proof.

For any $x\in\overline{\mathbf{R}}_{N}^{n}$ , let $\mathbf{a}$ be an arbitrary representative of the equivalence class $x$ . Then we have

$\displaystyle(\overline{R}toB\circ\overline{R}tr)(x)$	$\displaystyle=$	$\displaystyle(\overline{R}toB\circ\overline{R}tr)(\pi(\mathbf{a}))$
	$\displaystyle=$	$\displaystyle(\overline{R}toB\circ\overline{R}tr\circ\pi)(\mathbf{a})$
	$\displaystyle=$	$\displaystyle(\overline{R}toB\circ\pi\circ tr)(\mathbf{a})\hskip 28.45274pt(\mbox{by }(3.1))$
	$\displaystyle=$	$\displaystyle(RtoB\circ tr)(\mathbf{a})\hskip 45.5244pt(\mbox{by Proposition }2.6)$
	$\displaystyle=$	$\displaystyle(Btr\circ RtoB)(\mathbf{a})\hskip 36.98857pt(\mbox{by }(3.4))$
	$\displaystyle=$	$\displaystyle(Btr\circ\overline{R}toB\circ\pi)(\mathbf{a})\hskip 22.76219pt(\mbox{by Propotision }2.6)$
	$\displaystyle=$	$\displaystyle(Btr\circ\overline{R}toB)(x).$

This completes the proof of Corollary 3.2. ∎

3.2 Cyclicity of the Boolean average

Now we can prove the main result of this section, which asserts that only one of the components of $Bav$ determines the others completely:

Theorem 3.1.

$(1)$ The two self maps $Bav,Btr$ of the space $\mathbf{B}_{N}^{n}$ commute with each other:

\displaystyle Btr\circ Bav=Bav\circ Btr,

(3.7)

namely, the following diagram commutes:

\displaystyle\begin{CD}\mathbf{B}_{N}^{n}@>{Btr}>{}>\mathbf{B}_{N}^{n}\\ @V{Bav}V{}V@V{Bav}V{}V\\ \mathbf{B}_{N}^{n}@>{Btr}>{}>\mathbf{B}_{N}^{n}\\ \end{CD}

$(2)$ For any $i\in\mathbf{Z}_{N}$ , we denote by $Bav_{N}^{i}$ the composite $pr_{i}\circ Bav:\mathbf{B}_{N}^{n}\rightarrow\mathbf{F}_{2}$ , where $pr_{i}:\mathbf{F}_{2}^{N}\rightarrow\mathbf{F}_{2}$ is the projection onto the $i$ -th factor. Then we have

\displaystyle Btr^{*}(Bav_{N}^{i})=Bav_{N}^{i-_{N}1}.

(3.8)

Here the left hand side means the pull-back of the function $Bav_{N}^{i}$ through the self map $Btr$ on $\mathbf{B}_{N}^{n}$ , namely the composite $Bav_{N}^{i}\circ Btr$ .

Proof.

(1) Composing the left hand side of (3.6) with the bijection $\overline{R}toB$ , we compute as follows:

$\displaystyle Btr\circ Bav\circ\overline{R}toB$	$\displaystyle=$	$\displaystyle Btr\circ\overline{R}toB\circ\overline{R}av\hskip 28.45274pt(\mbox{by }(2.26))$
	$\displaystyle=$	$\displaystyle\overline{R}toB\circ\overline{R}tr\circ\overline{R}av\hskip 28.45274pt(\mbox{by }(3.5))$
	$\displaystyle=$	$\displaystyle\overline{R}toB\circ\overline{R}av\circ\overline{R}tr\hskip 28.45274pt(\mbox{by }(3.3))$
	$\displaystyle=$	$\displaystyle Bav\circ\overline{R}toB\circ\overline{R}tr\hskip 28.45274pt(\mbox{by }(2.26))$
	$\displaystyle=$	$\displaystyle Bav\circ Btr\circ\overline{R}toB\hskip 28.45274pt(\mbox{by }(3.5))$

This shows that the equality (3.6) holds.
(2) Note that we have

\displaystyle pr_{i}\circ Btr=pr_{i-_{N}1},

(3.9)

since for any $\mathbf{v}=(v_{0},v_{1},\cdots,v_{N-1})\in\mathbf{B}_{N}^{n}$ , we have

$\displaystyle(pr_{i}\circ Btr)(\mathbf{v})$	$\displaystyle=$	$\displaystyle pr_{i}(v_{N-1},v_{0},v_{1},\cdots,v_{N-2})$
	$\displaystyle=$	$\displaystyle v_{i-_{N}1}$
	$\displaystyle=$	$\displaystyle pr_{i-_{N}1}(\mathbf{v}).$

Hence we can compute as follows:

$\displaystyle Btr^{*}(Bav_{N}^{i})$	$\displaystyle=$	$\displaystyle Bav_{N}^{i}\circ Btr$
	$\displaystyle=$	$\displaystyle pr_{i}\circ Bav\circ Btr$
	$\displaystyle=$	$\displaystyle pr_{i}\circ Btr\circ Bav\hskip 34.1433pt(\Leftarrow\mbox{ by }(3.6))$
	$\displaystyle=$	$\displaystyle pr_{i-_{N}1}\circ Bav\hskip 42.67912pt(\Leftarrow\mbox{ by }(3.8))$
	$\displaystyle=$	$\displaystyle Bav_{N}^{i-_{N}1}.$

This completes the proof. ∎

Remark 3.1.

In concrete terms, the equality (3.7) means that every $Bav_{N}^{i}$ $(i\in\mathbf{Z}_{N})$ can be obtained by a cyclic coordinate change from $Bav_{N}^{0}$ .

4 Polynomial expression of the Boolean average

In this section we investigate how the Boolean average $Bav$ is expressed as a polynomial map on $\mathbf{B}_{N}$ . First we recall some standard method which translates any propositional functions into polynomial expressions.

4.1 Algebraic standard form of propositional functions

In this subsection we recall some standard facts about propositional functions. See [3,4] for details.
Let the truth-values $0$ and $1$ stand for ”false” and ”true”, respectively. Then any proposition can be regarded as an $\mathbf{F}_{2}$ -valued function on $\mathbf{F}_{2}^{N}$ for an appropriate $N$ . For example, the logical connective ”and” corresponds to the multiplication operator ” $\times$ ”, as is observed from the truth table of ”and”. On the other hand, the addition operator ” $+$ ” corresponds to the connective ”xor (exclusive or)”. Since any proposition can be expressed as a compound of these two connectives, it corresponds to a Boolean function of a certain number of variables. In view of the fact that we express a polynomial in several variables usually as a sum of monomials, the disjunctive normal form of logical formula plays a fundamental role for our purpose. We recall its construction by a typical example.
Example 4.1. The disjunctive normal form of $P=(x\vee y)\wedge(y\vee z)$ . The truth table of $P$ is given by

\displaystyle\begin{array}[]{lccccccccc}\mbox{number}&\vline&x&y&z&\vline&x\vee y&y\vee z&\vline&P\\ \hline\cr(1)&\vline&0&0&0&\vline&0&0&\vline&0\\ (2)&\vline&0&0&1&\vline&0&1&\vline&0\\ (3)&\vline&0&1&0&\vline&1&1&\vline&1\\ (4)&\vline&0&1&1&\vline&1&1&\vline&1\\ (5)&\vline&1&0&0&\vline&1&0&\vline&0\\ (6)&\vline&1&0&1&\vline&1&1&\vline&1\\ (7)&\vline&1&1&0&\vline&1&1&\vline&1\\ (8)&\vline&1&1&1&\vline&1&1&\vline&1\\ \end{array}

Table 4.1. Truth table for $P=(x\vee y)\wedge(y\vee z)$

There are five rows, named (3), (4), (6), (7), (8), for which the value of $P$ equals 1. We associate a term with each of these five rows. For example, the third row gives $P$ the value 1. We make a constituent of the corresponding term by the following rule. Here ” $w$ ” stands for any one of the variables $x,y,z$ :

	If the value of $w$ is 1, then use ” $w$ ”,
	otherwise use ” $\overline{w}$ ” as its constituent.

Therefore the third row provides us with the term $\overline{x}y\overline{z}$ , since $(x,y,z)=(0,1,0)$ . Connecting the term $\overline{x}y\overline{z}$ with the other four terms obtained from the remaining four rows, we obtain the following disjunctive normal form of the proposition $P$ :

\displaystyle P=\overline{x}y\overline{z}\vee\overline{x}yz\vee x\overline{y}z\vee xy\overline{z}\vee xyz.

Note that we can replace all ” $\vee$ ” by ” $\underline{\vee}$ ”, since each term on the right hand side contradicts to each other. Therefore we can rewrite this as

\displaystyle P=\overline{x}y\overline{z}\hskip 2.84526pt\underline{\vee}\hskip 2.84526pt\overline{x}yz\hskip 2.84526pt\underline{\vee}\hskip 2.84526ptx\overline{y}z\hskip 2.84526pt\underline{\vee}\hskip 2.84526ptxy\overline{z}\hskip 2.84526pt\underline{\vee}\hskip 2.84526ptxyz.

By letting $\overline{w}=1+w$ for each variable $w\in\{x,y,z\}$ , and by reducing the result modulo 2, we arrive at the following expression $B_{P}$ of $P$ as a Boolean polynomial:

$\displaystyle B_{P}$	$\displaystyle=$	$\displaystyle(1+x)y(1+z)+(1+x)yz+x(1+y)z+xy(1+z)+xyz$
	$\displaystyle=$	$\displaystyle 5xyz+2xy+2yz+xz+y$
	$\displaystyle=$	$\displaystyle xyz+xz+y.$

One can check that the rightmost side $xyz+xz+y$ coincides with $P$ as a function on $\mathbf{F}_{2}^{3}$ .

Remark 4.1.

In general, any Boolean polynomial $f(x_{1},\cdots,x_{n})$ should be regarded as an object in $\mathbf{F}_{2}[x_{1},\cdots,x_{n}]/I$ , where $I$ denotes the ideal

\displaystyle I=(x_{1}^{2}-x_{1},\cdots,x_{n}^{2}-x_{n}).

In the example above, however, one does not need to reduce $B_{P}$ modulo the ideal $I$ , since it has no squared variables.

4.2 Rhythm polynomials

In this subsection we investigate the problem how the self map $Bav$ on $\mathbf{B}_{N}^{n}$ can be expressed as a polynomial map. Since $\mathbf{B}_{N}=\bigcup_{n=0}^{N}\mathbf{B}_{N}^{n}$ , we can extend the domain of the definition of the map $Bav$ to the whole $\mathbf{B}_{N}$ naturally. By abuse of language we also denote the extended map by $Bav$ . Furthermore the composite

\displaystyle Bav_{N}^{i}=pr_{i}\circ Bav:\mathbf{F}_{2}^{N}\rightarrow\mathbf{F}_{2}

is called the $i$ -th rhythm polynomial modulo $N$ . By Theorem 3.1, (2), every rhythm polynomial is obtained from the 0-th rhythm polynomial $Bav_{N}^{0}$ through a cyclic change of variables $v_{i}$ , $i\in\mathbf{Z}_{N}$ . Therefore we can focus our attention exclusively on $Bav_{N}^{0}$ .
First we examine the problem for the case $N=3$ . The following table displays the Boolean averages of vectors in $\mathbf{B}_{3}$ . Recall that $Bav=ItoB\circ Iav\circ BtoI$ by (2.27):

\displaystyle\begin{array}[]{ccccccc}\mathbf{v}&\vline&BtoI(\mathbf{v})&\vline&Iav(BtoI(\mathbf{v}))&\vline&Bav(\mathbf{v})\\ \hline\cr(0,0,0)&\vline&\phi&\vline&\phi&\vline&(0,0,0)\\ (0,0,1)&\vline&(2)&\vline&(2)&\vline&(0,0,1)\\ (0,1,0)&\vline&(1)&\vline&(1)&\vline&(0,1,0)\\ (0,1,1)&\vline&(1,2)&\vline&(0,1)&\vline&(1,1,0)\\ (1,0,0)&\vline&(0)&\vline&(0)&\vline&(1,0,0)\\ (1,0,1)&\vline&(0,2)&\vline&(1,2)&\vline&(0,1,1)\\ (1,1,0)&\vline&(0,1)&\vline&(0,2)&\vline&(1,0,1)\\ (1,1,1)&\vline&(0,1,2)&\vline&(0,1,2)&\vline&(1,1,1)\\ \end{array}

Table 4.2. Boolean averages of three-dimensional vectors

Employing the algorithm explained in the previous subsection, we have

$\displaystyle Bav_{3}^{0}(v_{0},v_{1},v_{2})$	$\displaystyle=$	$\displaystyle\overline{v_{0}}v_{1}v_{2}+v_{0}\overline{v_{1}}\overline{v_{2}}+v_{0}v_{1}\overline{v_{2}}+v_{0}v_{1}v_{2}$
	$\displaystyle=$	$\displaystyle v_{0}+v_{0}v_{2}+v_{1}v_{2},$
$\displaystyle Bav_{3}^{1}(v_{0},v_{1},v_{2})$	$\displaystyle=$	$\displaystyle\overline{v_{0}}v_{1}\overline{v_{2}}+\overline{v_{0}}v_{1}v_{2}+v_{0}\overline{v_{1}}v_{2}+v_{0}v_{1}v_{2}$
	$\displaystyle=$	$\displaystyle v_{1}+v_{0}v_{1}+v_{0}v_{2},$
$\displaystyle Bav_{3}^{2}(v_{0},v_{1},v_{2})$	$\displaystyle=$	$\displaystyle\overline{v_{0}}\overline{v_{1}}v_{2}+v_{0}\overline{v_{1}}v_{2}+v_{0}v_{1}\overline{v_{2}}+v_{0}v_{1}v_{2}$
	$\displaystyle=$	$\displaystyle v_{2}+v_{0}v_{1}+v_{1}v_{2}.$

This computation confirms the cyclicity stated in Theorem 3.1, (2).
In a similar way we can compute the rhythm polynomial $Bav_{N}^{0}$ for small $N$ . We list the results as follows:

\displaystyle\begin{array}[]{cl}N&Bav_{N}^{0}\\ \hline\cr 3&v_{0}+v_{0}v_{2}+v_{1}v_{2}\\ 4&v_{0}+v_{0}v_{2}+v_{0}v_{3}+v_{1}v_{3}+v_{2}v_{3}+v_{0}v_{1}v_{2}+v_{1}v_{2}v_{3}\\ 5&v_{0}+v_{0}v_{2}+v_{0}v_{3}+v_{0}v_{4}+v_{1}v_{4}+v_{2}v_{3}+v_{2}v_{4}+v_{0}v_{1}v_{2}+v_{0}v_{1}v_{3}\\ &+v_{0}v_{3}v_{4}+v_{1}v_{2}v_{3}+v_{1}v_{2}v_{4}+v_{2}v_{3}v_{4}+v_{0}v_{1}v_{3}v_{4}+v_{1}v_{2}v_{3}v_{4}\\ \end{array}

Table 4.3. $Bav_{N}^{0}$ for $N=3,4,5$ in variables $v_{i}$

We observe here that for each $N\in\{3,4,5\}$ the number of terms in $Bav_{N}^{0}$ is equal to $2^{N-1}-1$ . If we change, however, the variables $v_{i}$ to $w_{i}+1$ for $i\in[0,N-1]$ , the number of terms diminishes to $2(N-1)$ , as is observed in the following list:

\displaystyle\begin{array}[]{cl}N&Bav_{N}^{0}\\ \hline\cr 3&1+w_{1}+w_{0}w_{2}+w_{1}w_{2}\\ 4&1+w_{1}+w_{0}w_{1}+w_{0}w_{3}+w_{0}w_{1}w_{2}+w_{1}w_{2}w_{3}\\ 5&1+w_{1}+w_{0}w_{1}+w_{0}w_{4}+w_{0}w_{1}w_{2}+w_{0}w_{1}w_{4}\\ &+w_{0}w_{1}w_{3}w_{4}+w_{1}w_{2}w_{3}w_{4}\\ 6&1+w_{1}+w_{0}w_{1}+w_{0}w_{5}+w_{0}w_{1}w_{2}+w_{0}w_{1}w_{5}\\ &+w_{0}w_{1}w_{2}w_{5}+w_{0}w_{1}w_{4}w_{5}+w_{0}w_{1}w_{2}w_{3}w_{5}+w_{1}w_{2}w_{3}w_{4}w_{5}\\ \end{array}

Table 4.4. $Bav_{N}^{0}$ for $N=3,4,5,6$ in variables $w_{i}$

At this point, we can imagine neither the general shape of $Bav_{N}^{0}$ , nor a possible relation between $Bav_{N}^{0}$ and $Bav_{N+1}^{0}$ . We will show that, if we change the index set $\mathbf{Z}_{N}$ to $\mathbf{Z}_{N,\pm}$ , the set of the least absolute remainders modulo $N$ , as a new index set, then we can detect the structure of $Bav_{N}^{0}$ more easily. When $N$ is even, we choose $\frac{N}{2}$ from the two possible representatives $\{-\frac{N}{2},\frac{N}{2}\}$ as the remainder, and hence the set $\mathbf{Z}_{N,\pm}$ is specified as

\displaystyle\mathbf{Z}_{N,\pm}=\left\{\begin{array}[]{ll}\{-m,-m+1,\cdots,-1,0,1,\cdots,m-1,m\},&\mbox{ if $N=2m+1$},\\ \{-m+1,\cdots,-1,0,1,\cdots,m-1,m\},&\mbox{ if $N=2m$}.\\ \end{array}\right.

By employing the floor symbol, we can express the set $\mathbf{Z}_{N,\pm}$ regardless of the parity of $N$ as follows:

\displaystyle\mathbf{Z}_{N,\pm}=[-\left\lfloor\frac{N-1}{2}\right\rfloor,\left\lfloor\frac{N}{2}\right\rfloor].

(4.6)

For later use, we divide the set $\mathbf{Z}_{N,\pm}$ into the following three parts:

\displaystyle\mathbf{Z}_{N,\pm}=\mathbf{Z}_{N,-}\sqcup\{0\}\sqcup\mathbf{Z}_{N,+},

where

	$\displaystyle\mathbf{Z}_{N,-}$	$\displaystyle=$	$\displaystyle\{k\in\mathbf{Z}_{N,\pm};k<0\},$
	$\displaystyle\mathbf{Z}_{N,+}$	$\displaystyle=$	$\displaystyle\{k\in\mathbf{Z}_{N,\pm};k>0\},$

and put

\displaystyle\mathbf{Z}_{N,\leq 0}

\displaystyle=

\displaystyle\mathbf{Z}_{N,-}\cup\{0\}.

We construct a bridge between $\mathbf{Z}_{N}$ and $\mathbf{Z}_{N,\pm}$ employing a simple bijection defined as follows:

Definition 4.1.

Let $rem_{\pm}:\mathbf{Z}\rightarrow\mathbf{Z}_{N,\pm}$ denote the map whose value at $k\in\mathbf{Z}$ is the least absolute remainder of $k$ modulo $N$ . Let $\varphi_{N}:\mathbf{Z}_{N}\rightarrow\mathbf{Z}_{N,\pm}$ denote the composite $rem_{\pm}\circ\iota$ , where $\iota:\mathbf{Z}_{N}\rightarrow\mathbf{Z}$ is the natural inclusion map, namely, $\varphi_{N}$ is a bijection between $\mathbf{Z}_{N}$ and $\mathbf{Z}_{N,\pm}$ defined by

\displaystyle\varphi_{N}(k)=\left\{\begin{array}[]{ll}k,&\mbox{ if }0\leq k\leq\left\lfloor\frac{N}{2}\right\rfloor,\\ k-N,&\mbox{ if }\left\lfloor\frac{N}{2}\right\rfloor<k\leq N-1.\\ \end{array}\right.

Remark 4.2.

The map $\varphi_{N}$ satisfies the condition

\displaystyle\varphi_{N}(a)\equiv a\pmod{N}

(4.8)

for any $a\in\mathbf{Z}_{N}$ . Therefore $\varphi_{N}$ exchanges the two representatives in $\mathbf{Z}_{N}$ and in $\mathbf{Z}_{N,\pm}$ of a class in the quotient $\mathbf{Z}/N\mathbf{Z}$ .

We introduce new variables $y_{j}$ , $j\in\mathbf{Z}_{N,\pm}$ , by the rule

\displaystyle w_{i}=y_{\phi_{N}(i)}

for any $i\in\mathbf{Z}_{N}$ . Then Table 4.4 transforms to the following:

\displaystyle\begin{array}[]{cl}N&Bav_{N}^{0}\\ \hline\cr 3&1+y_{1}+y_{0}y_{-1}+y_{1}y_{-1}\\ 4&1+y_{1}+y_{0}y_{1}+y_{0}y_{-1}+y_{0}y_{1}y_{2}+y_{1}y_{2}y_{-1}\\ 5&1+y_{1}+y_{0}y_{1}+y_{0}y_{-1}+y_{0}y_{1}y_{2}+y_{0}y_{1}y_{-1}\\ &+y_{0}y_{1}y_{-2}y_{-1}+y_{1}y_{2}y_{-2}y_{-1}\\ 6&1+y_{1}+y_{0}y_{1}+y_{0}y_{-1}+y_{0}y_{1}y_{2}+y_{0}y_{1}y_{-1}\\ &+y_{0}y_{1}y_{2}y_{-1}+y_{0}y_{1}y_{-1}y_{-1}\\ &+y_{0}y_{1}y_{2}y_{3}y_{-1}+y_{1}y_{2}y_{3}y_{-2}y_{-1}\\ \end{array}

Table 4.5. $Bav_{N}^{0}$ for $N=3,4,5,6$ in variables $y_{i}$ , $i\in\mathbf{Z}_{N,\pm}$

This table suggests us the structure of the rhythm polynomial $Bav_{N}^{0}$ more clearly than Table 4.4. We explore in the next section the true nature of these polynomials.

5 Determination of rhythm polynomials

In this section we determine the Boolean polynomial $Bav_{N}^{0}$ completely for any $N$ , and derive a recurrence formula which connects $Bav_{N}^{0}$ and $Bav_{N-1}^{0}$ . Furthermore we prove that $Bav_{N}^{0}$ is a balanced polynomial. (See Definition 5.10.)

5.1 Change of the set of indices

As is motivated in Subsection 4.2, we need to use two index sets $\mathbf{Z}_{N}$ and $\mathbf{Z}_{N,\pm}$ properly to understand the rhythm polynomials. Fortunately enough, even if we employ $\mathbf{Z}_{N,\pm}$ as the index set, several corresponding objects can be defined in almost the same way.
By abuse of language, we denote also by $\varphi_{N}$ the bijective map $\mathbf{Z}_{N}^{n}\rightarrow\mathbf{Z}_{N,\pm}^{n}$ induced by $\varphi_{N}$ between their self-products, and put

\displaystyle\mathbf{R}_{N,\pm}^{n}=\varphi_{N}(\mathbf{R}_{N}^{n}).

Definition 5.1.

Let $\mathbf{I}_{N,\pm}^{n}$ denote the subset of $\mathbf{R}_{N,\pm}^{n}$ which consists of the monotone increasing sequence:

\displaystyle\mathbf{I}_{N,\pm}^{n}=\{\mathbf{a}=(a_{0},\cdots,a_{n-1})\in\mathbf{R}_{N,\pm}^{n};a_{0}<a_{1}<\cdots<a_{n-1}\}.

Definition 5.2.

Let $\mathbf{B}_{N,\pm}$ denote the set of $n$ -dimensional Boolean vectors with index set $\mathbf{Z}_{N,\pm}$ , namely,

\displaystyle\mathbf{B}_{N,\pm}=\{(v_{\ell},\cdots,v_{g});v_{i}\in\mathbf{F}_{2}\mbox{ for any }i\in[\ell,g]\},

where we introduce the two symbols $\ell,g$ by

\displaystyle\ell=-\left\lfloor\frac{N-1}{2}\right\rfloor,\hskip 5.69054ptg=\left\lfloor\frac{N}{2}\right\rfloor,

which are the least and the greatest elements in $\mathbf{Z}_{N,\pm}$ .

We use the same symbol $ItoB$ and $BtoI$ as before to denote the pair of bijections between $\mathbf{I}_{N,\pm}^{n}$ and $\mathbf{B}_{N,\pm}^{n}$ , which are defined as follows:

Definition 5.3.

$(1)$ For any $\mathbf{a}\in\mathbf{I}_{N,\pm}^{n}$ , the Boolean vector $\mathbf{v}=(v_{\ell},\cdots,v_{g})=ItoB(\mathbf{a})\in\mathbf{B}_{N,\pm}$ is defined by

\displaystyle v_{i}=\left\{\begin{array}[]{ll}1,&\mbox{ if }i\in\mathbf{a},\\ 0,&\mbox{ if }i\not\in\mathbf{a}.\\ \end{array}\right.

(5.3)

$(2)$ For any $\mathbf{v}\in\mathbf{B}_{N,\pm}^{n}$ , the $n$ -tuple $BtoI(\mathbf{v})\in\mathbf{I}_{N,\pm}^{n}$ is defined to be the unique arrangement of the set $\{i\in\mathbf{Z}_{N,\pm};v_{i}=1\}$ in increasing order.

5.2 Parental pair and ancestor of zero in $\mathbf{Z}_{N}$

It is important to keep in mind the following fact:

Lemma 5.1.

The $0$ -th rhythm polynomial $Bav_{N}^{0}$ takes value $1$ at $\mathbf{v}\in\mathbf{B}_{N}$ if and only if

\displaystyle 0\in Rav(BtoI(\mathbf{v})).

Proof.

Let $\mathbf{a}=(a_{0},\cdots,a_{n-1})=BtoI(\mathbf{v})\in\mathbf{I}_{N}^{n}$ . Since it is in $\mathbf{I}_{N}^{n}$ , we have

\displaystyle Iav(\mathbf{a})=Rav(\mathbf{a}).

Recall that the two maps $Iav$ and $Bav$ are compatible through the map $ItoB$ by Proposition 2.9. Hence we have the following series of equivalences:

$\displaystyle 0\in Rav(\mathbf{a})$	$\displaystyle\Leftrightarrow$	$\displaystyle 0\in Iav(\mathbf{a})$
	$\displaystyle\Leftrightarrow$	$\displaystyle 0\in(BtoI\circ Bav\circ ItoB)(\mathbf{a})\hskip 28.45274pt(\mbox{by }(2.27))$
	$\displaystyle\Leftrightarrow$	$\displaystyle 0\in(BtoI\circ Bav)(\mathbf{v})$
	$\displaystyle\Leftrightarrow$	$\displaystyle 0\in supp(Bav(\mathbf{v}))\hskip 71.13188pt(\mbox{by }(2.12))$
	$\displaystyle\Leftrightarrow$	$\displaystyle pr_{0}(Bav(\mathbf{v}))=1$
	$\displaystyle\Leftrightarrow$	$\displaystyle Bav_{N}^{0}(\mathbf{v})=1.$

Thus we finish the proof. ∎

By this lemma, in order to find the form of $Bav_{N}^{0}$ , it is essential to determine the set of pairs $(a,b)\in\mathbf{Z}_{N}\times\mathbf{Z}_{N}$ such that $av_{\mathbf{Z}_{N}}(a,b)=0$ . This leads us to the following:

Definition 5.4.

A pair $(a,b)\in\mathbf{Z}_{N}\times\mathbf{Z}_{N}$ is said to be a parental pair of zero if $av_{\mathbf{Z}_{N}}(a,b)=0$ . A rhythm $\mathbf{a}\in\mathbf{R}_{N}$ is called an ancestor of zero if $0\in Rav(\mathbf{a})$ .

The following proposition provides us with a necessary and sufficient condition for a pair to be a parental pair of zero. It is expressed as a congruence modulo $N$ . This will facilitate our transition from $\mathbf{Z}_{N}$ to $\mathbf{Z}_{N,\pm}$ in the next subsection.

Proposition 5.1.

Let $a,b$ be an arbitrary pair of elements in $\mathbf{Z}_{N}$ .
$(0)$ When $a=0$ , the following conditions are equivalent:
$(0.{\rm A})\hskip 2.84526ptav_{\mathbf{Z}_{N}}(a,b)=0$ ,
$(0.{\rm B})\hskip 2.84526ptb=0,1$ .
$(1)$ When $a=1$ , these exists no $b\in\mathbf{Z}_{N}$ such that $av_{\mathbf{Z}_{N}}(a,b)=0$ .
$(2)$ When $a\geq 2$ , the following conditions are equivalent:
$(2.{\rm A})\hskip 2.84526ptav_{\mathbf{Z}_{N}}(a,b)=0$ ,
$(2.{\rm B})\hskip 2.84526pta>b\mbox{ and }a+b\equiv 0,1\pmod{N}$ .

Remark 5.1.

When $n\geq 2$ , an element in $\mathbf{R}_{N}^{n}$ consists of $n$ distinct elements of $\mathbf{Z}_{N}$ by the definition. Hence the first alternative in $(0.{\rm B})$ , namely the case when $(a,b)=(0,0)$ occurs only if $n=1$ . In that case, the discrete average $Rav((0))$ of the one-element rhythm $(0)$ is $(0)$ .

Proof.

(0) When $a=0$ , we have

\displaystyle av_{\mathbf{Z}_{N}}(0,b)=\left\lfloor\frac{b}{2}\right\rfloor,

and hence it is equal to $0$ if and only if $b=0,1$ . Therefore (0.A) and (0.B) are equivalent.
(1) When $a=1$ , if $av_{\mathbf{Z}_{N}}(1,b)=0$ , then $0\in[1,b]_{N}$ by Proposition 1.2, (2). This occurs only if $b=0$ . When $N$ is odd and $N=2m+1$ , we have

$\displaystyle av_{\mathbf{Z}_{N}}(1,0)$	$\displaystyle=$	$\displaystyle 1+_{N}\left\lfloor\frac{0-_{N}1}{2}\right\rfloor$
	$\displaystyle=$	$\displaystyle 1+_{N}\left\lfloor\frac{N-1}{2}\right\rfloor$
	$\displaystyle=$	$\displaystyle 1+_{N}m.$

Note that $1+_{N}m=1+m<1+2m=N$ , and hence $1+_{N}m$ cannot be equal to 0. When $N$ is even and $N=2m$ , it follows by a similar computation that $av_{\mathbf{Z}_{N}}(1,0)=1+_{N}(m-1)$ , which cannot be zero. This completes the proof of the assertion (1).
(2) (2.A) $\Rightarrow$ (2.B): Since $av_{\mathbf{Z}_{N}}(a,b)\in[a,b]_{N}$ by Proposition 1.2, (2), the condition $av_{\mathbf{Z}_{N}}(a,b)=0$ implies that $0\in[a,b]$ , and hence $a>b$ . Furthermore the equality $av_{\mathbf{Z}_{N}}(a,b)=a+_{N}\left\lfloor\frac{b-_{N}a}{2}\right\rfloor=0$ holds if and only if

\displaystyle\left\lfloor\frac{b-_{N}a}{2}\right\rfloor=N-a,

(5.4)

since $a\neq 0$ . Note that

\displaystyle 2\left\lfloor\frac{x}{2}\right\rfloor=\left\{\begin{array}[]{ll}x,&\mbox{ if }x\equiv 0\pmod{2},\\ x-1,&\mbox{ if }x\equiv 1\pmod{2},\\ \end{array}\right.

for any $x\in\mathbf{Z}$ . When $b-_{N}a\equiv 0\pmod{2}$ , doubling the both sides of (5.2), we have

\displaystyle b-_{N}a=2N-2a,

which gives us the congruence

\displaystyle a+b\equiv 0\pmod{N}.

When $b-_{N}a\equiv 1\pmod{2}$ , the equality (5.2) implies similarly that

\displaystyle b-_{N}a-1=2N-2a,

which gives us the congruence

\displaystyle a+b\equiv 1\pmod{N}.

Thus (2.A) implies (2.B).
(2.B) $\Rightarrow$ (2.A): In case $a+b\equiv 0\pmod{N}$ , we have $b=N-a$ since $a>0$ . Furthermore, since $a>b$ , we have $a>N-a$ , therefore $0>N-2a>-N$ . It follows that

$\displaystyle b-_{N}a$	$\displaystyle=$	$\displaystyle(N-a)-_{N}a$
	$\displaystyle=$	$\displaystyle\langle(N-a)-a\rangle_{N}$
	$\displaystyle=$	$\displaystyle\langle N-2a\rangle_{N}$
	$\displaystyle=$	$\displaystyle 2N-2a.$

Hence we have

$\displaystyle av_{\mathbf{Z}_{N}}(a,b)$	$\displaystyle=$	$\displaystyle a+_{N}\left\lfloor\frac{b-_{N}a}{2}\right\rfloor$
	$\displaystyle=$	$\displaystyle a+_{N}\left\lfloor\frac{2N-2a}{2}\right\rfloor$
	$\displaystyle=$	$\displaystyle a+_{N}(N-a)$
	$\displaystyle=$	$\displaystyle 0.$

In case $a+b\equiv 1\pmod{N}$ , we have $b=N+1-a$ , since we have assumed that $a\geq 2$ . Since $a>b$ , we have $a>N+1-a$ , therefore $0>N+1-2a>-N$ . It follows that

$\displaystyle b-_{N}a$	$\displaystyle=$	$\displaystyle(N+1-a)-_{N}a$
	$\displaystyle=$	$\displaystyle\langle(N+1-a)-a\rangle_{N}$
	$\displaystyle=$	$\displaystyle\langle N+1-2a\rangle_{N}$
	$\displaystyle=$	$\displaystyle 2N+1-2a.$

Hence we have

$\displaystyle av_{\mathbf{Z}_{N}}(a,b)$	$\displaystyle=$	$\displaystyle a+_{N}\left\lfloor\frac{b-_{N}a}{2}\right\rfloor$
	$\displaystyle=$	$\displaystyle a+_{N}\left\lfloor\frac{2N+1-2a}{2}\right\rfloor$
	$\displaystyle=$	$\displaystyle a+_{N}(N-a)$
	$\displaystyle=$	$\displaystyle 0.$

This completes the proof. ∎

Corollary 5.1.

When $a\in[1,N/2]$ , there exists no $b\in\mathbf{Z}_{N}$ such that $av_{\mathbf{Z}_{N}}(a,b)$
$=0$ .

Proof.

By Proposition 5.1, (1), we may assume that $2\leq a\leq N/2$ . Suppose that $av_{\mathbf{Z}_{N}}(a,b)=0$ holds for some $b\in\mathbf{Z}_{N}$ . Then it follows from Proposition 5.1, (2) that $a+b\equiv 0,1\pmod{N}$ , which implies $b=N-a$ or $b=N+1-a$ . Since $a>b$ by (2.B), we have $2a>N$ or $2a>N+1$ , and hence $a>N/2$ in both cases. This contradiction finishes the proof. ∎

5.3 Parental pair and ancestor of zero in $\mathbf{Z}_{N,\pm}$

In this subsection, we show that, if we employ the index set $\mathbf{Z}_{N,\pm}$ instead of $\mathbf{Z}_{N}$ , then the assertions of Proposition 5.1 and Corollary 5.1 are simplified considerably.

Definition 5.5.

For any $(a,b)\in\mathbf{Z}_{N,\pm}\times\mathbf{Z}_{N,\pm}$ , $\mathbf{Z}_{N,\pm}$ -average $av_{\mathbf{Z}_{N},\pm}(a,b)$ is defined by

\displaystyle av_{\mathbf{Z}_{N},\pm}(a,b)=\varphi_{N}(av_{\mathbf{Z}_{N}}(\varphi_{N}^{-1}(a),\varphi_{N}^{-1}(b))).

Furthermore, on $\mathbf{R}_{N,\pm}^{n}=\varphi_{N}(\mathbf{R}_{N}^{n})$ , we define $\pm$ -discrete average transformation $Rav_{\pm}:\mathbf{R}_{N,\pm}^{n}\rightarrow\mathbf{R}_{N,\pm}^{n}$ by

\displaystyle Rav_{\pm}(\mathbf{a})=\varphi_{N}(Rav(\varphi_{N}^{-1}(\mathbf{a})))

for any $\mathbf{a}\in\mathbf{R}_{N,\pm}^{n}$ .

The two notions, parental pairs and ancestors of zero, introduced in the previous subsection, are translated as follows:

Definition 5.6.

A pair $(a,b)\in\mathbf{Z}_{N,\pm}\times\mathbf{Z}_{N,\pm}$ is said to be a parental pair of zero if $rav_{\pm}(a,b)=0$ . We denote the set of parental pairs of zero in $\mathbf{Z}_{N,\pm}\times\mathbf{Z}_{N,\pm}$ by $Par_{N}$ :

\displaystyle Par_{N}=\{(a,b)\in\mathbf{Z}_{N,\pm}\times\mathbf{Z}_{N,\pm};rav_{\pm}(a,b)=0\}.

A rhythm $\mathbf{a}\in\mathbf{R}_{N,\pm}$ is called an ancestor of zero if $0\in Rav_{\pm}(\mathbf{a})$ .

We can determine the set $Par_{N}$ completely in the following way:

Proposition 5.2.

$(0)$ If $(a,b)\in Par_{N}$ , then $a\in\mathbf{Z}_{N,\leq 0}=\mathbf{Z}_{N,-}\cup\{0\}$ .
$(1)$ We have

\displaystyle Par_{N}=Par_{N}^{0}\sqcup Par_{N}^{1},

where

	$\displaystyle Par_{N}^{0}$	$\displaystyle=$	$\displaystyle\{(-k,k);0\leq k\leq\lfloor\frac{N-1}{2}\rfloor\}\subset\mathbf{Z}_{N,\pm}\times\mathbf{Z}_{N,\pm},$
	$\displaystyle Par_{N}^{1}$	$\displaystyle=$	$\displaystyle\{(-k,k+1);0\leq k\leq\lfloor\frac{N-2}{2}\rfloor\}\subset\mathbf{Z}_{N,\pm}\times\mathbf{Z}_{N,\pm}.$

In particular there are $N$ parental pairs of zero for any $N$ .

Proof.

(0) By Definition 5.5, if $rav_{\pm}(a,b)=0$ , then

\displaystyle rav(\varphi_{N}^{-1}(a),\varphi_{N}^{-1}(b))=\varphi_{N}^{-1}(0)=0.

This implies by Corollary 5.1 that $\varphi_{N}^{-1}(a)=0$ or $\frac{N}{2}<\varphi_{N}^{-1}(a)\leq N-1$ , which is equivalent to the condition that $a\in\mathbf{Z}_{N,\leq 0}$ .

(1) Suppose that $(a,b)\in Par_{N}$ . Since we have $(0,0),(0,1)\in Par_{N}$ by Proposition 5.1, (0), we may assume that $a\neq 0$ , and hence $a\in\mathbf{Z}_{N,-}$ . The latter implies in particular that $\varphi_{N}^{-1}(a)\geq 2$ . Therefore it follows from Proposition 5.3, (2) that

\displaystyle\varphi_{N}^{-1}(a)+\varphi_{N}^{-1}(b)\equiv 0,1\pmod{N}.

This is equivalent to

\displaystyle a+b\equiv 0,1\pmod{N}

(5.6)

by Remark 4.2. Since we can put $a=-k$ with $k\in[1,\lfloor\frac{N-1}{2}\rfloor]$ , the condition (5.3) implies that $b=k$ or $b=k+1$ . The latter alternative is excluded only when $N$ is odd and $k=\frac{N-1}{2}$ by the shape of $\mathbf{Z}_{N,\pm}$ . The last assertion follows from the equality

\displaystyle|Par_{N}^{0}|+|Par_{N}^{1}|=(\lfloor\frac{N-1}{2}\rfloor+1)+(\lfloor\frac{N-2}{2}\rfloor+1)=N.

This completes the proof. ∎

For small $N$ , the set $Par_{N}$ is given by the following:

\displaystyle\begin{array}[]{lcl}N&\vline&Par_{N}\\ \hline\cr 3&\vline&(0,0),(0,1),(-1,1)\\ 4&\vline&(0,0),(0,1),(-1,1),(-1,2)\\ 5&\vline&(0,0),(0,1),(-1,1),(-1,2),(-2,2)\\ 6&\vline&(0,0),(0,1),(-1,1),(-1,2),(-2,2),(-2,3)\\ \end{array}

Table 5.1. $Par_{N}$ for $N=3,4,5,6$

Remark 5.2.

When $n=1$ , there is only one ancestor of zero in $\mathbf{R}_{N,\pm}^{1}$ , namely, the singleton $(0)$ . This is because the discrete average map $Rav_{\pm}$ is defined to be the identity map on $\mathbf{R}_{N,\pm}^{1}$ . For this reason we assume $n\geq 2$ from now on.

Based on Proposition 5.2, we can understand completely the structure of the set of ancestors of zero, and hence the shape of the rhythm polynomial $Bav_{N}^{0}$ . The following proposition is a rephrasing of Definition 5.4:

Proposition 5.3.

When $n\geq 2$ , an element $\mathbf{a}=(a_{0},\cdots,a_{n-1})\in\mathbf{R}_{N,\pm}^{n}$ is an ancestor of zero if and only if there exists an index $i\in\mathbf{Z}_{n}$ such that $(a_{i},a_{i+_{n}1})\in Par_{N}$ .

In view of this, we introduce the following:

Definition 5.7.

For any $(a,b)\in Par_{N}\setminus\{(0,0)\}$ and for any $n\in[2,N]$ , we put

\displaystyle Anc_{(a,b)}^{n}=\{\mathbf{a}\in\mathbf{I}_{N,\pm}^{n};(a_{i},a_{i+_{n}1})=(a,b)\mbox{ for some }i\in\mathbf{Z}_{n}\},

and

\displaystyle Anc_{(a,b)}=\bigcup_{n=2}^{N}Anc_{(a,b)}^{n}.

(5.8)

When $(a,b)=(0,0)$ , we put

\displaystyle Anc_{(0,0)}=\{(0)\}.

Collecting these families of ancestors, we put

\displaystyle Anc_{N}=\bigcup_{(a,b)\in Par_{N}}Anc_{(a,b)},

and call it the set of ancestors of zero.

In order to formulate a Boolean counterpart of the notion of ancestor of zero, we put

	$\displaystyle[a,b]_{N,\pm}$	$\displaystyle=$	$\displaystyle\varphi_{N}([\varphi_{N}^{-1}(a),\varphi_{N}^{-1}(b)]_{N}),$		(5.9)
	$\displaystyle\mbox{$[$}a,b)_{N,\pm}$	$\displaystyle=$	$\displaystyle[a,b]_{N,\pm}\setminus\{b\}$		(5.10)

for any $(a,b)\in\mathbf{Z}_{N,\pm}\times\mathbf{Z}_{N,\pm}$ . Then we have the following:

Proposition 5.4.

Fix an arbitrary $(a,b)\in Par_{N}\setminus\{(0,0)\}$ . For any $\mathbf{a}\in\mathbf{I}_{N,\pm}^{n}$ with $n\geq 2$ , let $\mathbf{v}=ItoB(\mathbf{a})\in\mathbf{B}_{N,\pm}$ . Then the following three conditions are equivalent:
$(1)$ $\mathbf{a}\in Anc_{(a,b)}$ .
$(2)$ $\mathbf{a}\cap[a,b]_{N,\pm}=\{a,b\}$ .
$(3)$ $v_{a}=1,v_{a+_{N}1}=0,\cdots,v_{b-_{N}1}=0,v_{b}=1$ .

Remark 5.3.

Here in the item (3), we denote the addition on $\mathbf{Z}_{N,\pm}$ also by ” $+_{N}$ ”, which is used originally for the addition on $\mathbf{Z}_{N}$ . Strictly speaking, for any $(a,b)\in\mathbf{Z}_{N,\pm}\times\mathbf{Z}_{N,\pm}$ , we should define a new addition ” $a+_{N,\pm}b$ ” by the rule

\displaystyle a+_{N,\pm}b=\varphi_{N}(\varphi_{N}^{-1}(a)+_{N}\varphi_{N}^{-1}(b)).

We, however, abuse the notation, since the context will tell us which meaning we are adopting.

Proof.

$(1)\Rightarrow(2)$ : Let $\mathbf{a}=(a_{0},\cdots,a_{n-1})$ . The statement (1) implies by Definition 5.7 that there exists an index $i\in\mathbf{Z}_{n}$ such that $(a_{i},a_{i+_{n}1})=(a,b)$ . On the other hand, by (1.8), we have

\displaystyle\mathbf{Z}_{N,\pm}=\bigsqcup_{j\in\mathbf{Z}_{n}}[a_{j},a_{j+_{n}1})_{N,\pm}.

Since the right hand side is a disjoint union, we have $\mathbf{a}\cap[a,b]=\{a,b\}$ .

$(2)\Rightarrow(3)$ : By the definition of the map $ItoB$ , the $i$ -th coordinate $v_{i}$ , $i\in\mathbf{Z}_{N,\pm}$ , of $\mathbf{v}=ItoB(\mathbf{a})$ is given by

\displaystyle v_{i}=\left\{\begin{array}[]{ll}1,&i\in\mathbf{a},\\ 0,&i\not\in\mathbf{a}.\\ \end{array}\right.

Therefore the equality $\mathbf{a}\cap[a,b]_{N,\pm}=\{a,b\}$ in (2) implies the equalities $v_{a}=1,v_{a+_{N}1}=0,\cdots,v_{b-_{N}1}=0,v_{b}=1$ in the statement (3).

$(3)\Rightarrow(1)$ : It follows from (3) and the definition of $ItoB$ that there exists an $i\in\mathbf{Z}_{N,\pm}$ such that $a_{i}=a,a_{i+_{n}1}=b$ . Hence it follows from Definition 5.7 that the statement (1) holds true. This completes the proof. ∎

In view of this proposition, we introduce the notion of $\mathbf{B}$ -ancestor of zero as follows:

Definition 5.8.

Every element in $ItoB(Anc_{N})\subset\mathbf{B}_{N,\pm}$ are called a $\mathbf{B}$ -ancestor of zero. We denote by $\mathbf{B}$ - $Anc_{N}$ the set of $\mathbf{B}$ -ancestors of zero. Furthermore for each $(a,b)\in Par_{N}$ , we put

\displaystyle\mathbf{B}\mbox{-}Anc_{(a,b)}=ItoB(Anc_{(a,b)})

so that we have

\displaystyle\mathbf{B}\mbox{-}Anc_{N}=\bigcup_{(a,b)\in Par_{N}}\mathbf{B}\mbox{-}Anc_{(a,b)}

The following notation will simplify our description below:

Definition 5.9.

For any $(a,b)\in Par_{N}\setminus\{(0,0)\}$ , we denote by $\mathbf{e}_{[a,b]}\in\mathbf{F}_{2}^{b-a+1}$ the Boolean vector whose $i$ -th coordinate $\mathbf{e}_{[a,b]}^{i}$ $(1\leq i\leq b-a+1)$ is defined by

\displaystyle\mathbf{e}_{[a,b]}^{i}=\left\{\begin{array}[]{ll}1,&\mbox{ if }i=1\mbox{ or }i=b-a+1,\\ 0,&\mbox{ if }1<i<b-a+1.\\ \end{array}\right.

In other words, the vector $\mathbf{e}_{[a,b]}$ is a Boolean vector of length $|[a,b]|$ such that the first and the last coordinates are $1$ and the others are $0$ .

The equivalence of (1) and (3) in Proposition 5.4 implies the following:

Corollary 5.2.

For any $(a,b)\in Par_{N}\setminus\{(0,0)\}$ , let $pr_{[a,b]}:\mathbf{B}_{N,\pm}\rightarrow\mathbf{F}_{2}^{b-a+1}$ denote the projection defined by

\displaystyle pr_{[a,b]}(v_{\ell},\cdots,v_{g})=(v_{a},\cdots,v_{b}).

Then we have

\displaystyle\mathbf{B}\mbox{-}Anc_{(a,b)}=pr_{[a,b]}^{-1}(\mathbf{e}_{[a,b]}).

This implies further the following:

Corollary 5.3.

For any $(a,b)\in Par_{N}\setminus\{(0,0)\}$ , the number of elements in $Anc_{(a,b)}$ is given by

\displaystyle|Anc_{(a,b)}|=2^{N-1-(b-a)}.

Proof.

By the bijectivity of the map $ItoB$ , we have only to count the number of elements in $\mathbf{B}$ - $Anc_{[a,b]}$ , which coincides with $pr_{[a,b]}^{-1}(\mathbf{e}_{[a,b]})$ by Corollary 5.2. Hence we can compute as follows:

$\displaystyle\|Anc_{(a,b)}\|$	$\displaystyle=$	$\displaystyle\|\mathbf{B}\mbox{-}Anc_{(a,b)}\|$
	$\displaystyle=$	$\displaystyle\|pr_{[a,b]}^{-1}(\mathbf{e}_{[a,b]})\|$
	$\displaystyle=$	$\displaystyle 2^{N-(b-a+1)}.$

This finishes the proof. ∎

We can deduce from this corollary that the polynomial $Bav_{N}^{0}$ is balanced.

Definition 5.10.

A Boolean function $P:\mathbf{F}_{2}^{n}\rightarrow\mathbf{F}_{2}$ is said to be balanced if

\displaystyle|P^{-1}(\{0\})|=|P^{-1}(\{1\})|=2^{n-1}.

For the importance of the balanced polynomials in cryptology, we refer the reader to [4, Chapter 3].

Theorem 5.1.

The $0$ -th rhythm polynomial $Bav_{N}^{0}$ is balanced.

Proof.

The set of ancestors of zero is the disjoint union of $Anc_{(a,b)}$ $((a,b)\in Par_{N}\setminus\{(0,0)\})$ and $Anc_{(0,0)}$ . Hence the total is computed through Corollary 5.3 as follows:

	$\displaystyle\left(\sum_{(a,b)\in Par_{N}\setminus\{(0,0)\}}\|Anc_{(a,b)}\|\right)+\|Anc_{(0,0)}\|$
	$\displaystyle=\left(\sum_{(a,b)\in Par_{N}\setminus\{(0,0)\}}2^{N-1-(b-a)}\right)+1$
	$\displaystyle=\left(\sum_{(a,b)\in Par_{N}^{0}\setminus\{(0,0)\}}2^{N-1-(b-a)}+\sum_{(a,b)\in Par_{N}^{1}}2^{N-1-(b-a)}\right)+1$
	$\displaystyle=\left(\sum_{1\leq k\leq\lfloor\frac{N-1}{2}\rfloor}2^{N-1-(k-(-k))}+\sum_{0\leq k\leq\lfloor\frac{N-2}{2}\rfloor}2^{N-1-((k+1)-(-k))}\right)+1$
	$\displaystyle\hskip 199.16928pt(\mbox{by Proposition 5.2, (1))}$
	$\displaystyle=\left(\sum_{1\leq k\leq\lfloor\frac{N-1}{2}\rfloor}2^{N-1-2k}+\sum_{0\leq k\leq\lfloor\frac{N-2}{2}\rfloor}2^{N-1-(2k+1)}\right)+1$		(5.13)

Here we notice that the set $\{2k;1\leq k\leq\lfloor\frac{N-1}{2}\rfloor\}$ coincides with the set of positive even numbers in the interval $[0,N-1]$ , and that the set $\{2k+1;0\leq k\leq\lfloor\frac{N-2}{2}\rfloor\}$ coincides with the set of odd numbers in the interval $[0,N-1]$ . Therefore we have

\displaystyle\{2k;1\leq k\leq\lfloor\frac{N-1}{2}\rfloor\}\cup\{2k+1;0\leq k\leq\lfloor\frac{N-2}{2}\rfloor\}=[1,N-1]

Hence the rightmost side of (5.7) is equal to

\displaystyle\left(\sum_{1\leq j\leq N-1}2^{N-1-j}\right)+1=\left(\sum_{0\leq j\leq N-2}2^{j}\right)+1=2^{N-1}.

This completes the proof. ∎

5.4 Main theorem on the structure of the rhythm polynomial $Bav_{N}^{0}$

In order to state our main theorem on $Bav_{N}^{0}$ , we introduce some notations:

Definition 5.11.

For any $(a,b)\in Par_{N}\setminus\{(0,0)\}$ , we denote by $f_{[a,b]}$ the Boolean polynomial given by

\displaystyle f_{[a,b]}=(y_{a}+1)\left(\prod_{k=a+1}^{b-1}y_{k}\right)(y_{b}+1).

Furthermore we set

\displaystyle f_{[0,0]}^{N}=(y_{0}+1)\prod_{k\in\mathbf{Z}_{N,\pm}\setminus\{0\}}y_{k}.

Remark 5.4.

Notice that the definition of $f_{[a,b]}$ for any $[a,b]\in Par_{N}\setminus\{(0,0)\}$ does not depend on $N$ , but only on the values of $a,b$ . On the other hand the definition of $f_{[0,0]}^{N}$ depends on $N$ . This is why we put ” $N$ ” on the superscript.

The general form of the Boolean polynomial $Bav_{N}^{0}$ is given by the following:

Theorem 5.2.

For any $N\geq 3$ , we have

\displaystyle Bav_{N}^{0}=\sum_{(a,b)\in Par_{N}\setminus\{(0,0)\}}f_{[a,b]}+f_{[0,0]}^{N}.

(5.14)

Our proof of this theorem will be given later in the subsection 5.6, after we prepare several results concerning the algebraic standard forms of special Boolean functions.

5.5 Preliminaries for the proof of Theorem 5.2

For any $S=\{s_{1},\cdots,s_{k}\}\subset\mathbf{Z}_{N}$ , we denote by $pr_{S}:\mathbf{F}_{2}^{N}\rightarrow\mathbf{F}_{2}^{|S|}$ the projection defined by

\displaystyle pr_{S}(x_{0},\cdots,x_{N-1})=(x_{s_{1}},\cdots,x_{s_{k}})

for any $(x_{0},\cdots,x_{N-1})\in\mathbf{F}_{2}^{N}$ .

Proposition 5.5.

Let $P=P(x_{0},\cdots,x_{N-1}):\mathbf{F}_{2}^{N}\rightarrow\mathbf{F}_{2}$ be a Boolean function with the following property: There exists a subset $S=\{s_{1},\cdots,s_{k}\}\subset\mathbf{Z}_{N}$ such that

\displaystyle P^{-1}(\{1\})=pr_{S}^{-1}(\{(b_{1},\cdots,b_{k})\})

for some $(b_{1},\cdots,b_{k})\in\mathbf{F}_{2}^{k}$ . Then we have

\displaystyle P(x_{0},\cdots,x_{N-1})=x_{s_{1}}^{(b_{1})}x_{s_{2}}^{(b_{2})}\cdots x_{s_{k}}^{(b_{k})},

where we put

	$\displaystyle x_{i}^{(0)}$	$\displaystyle=$	$\displaystyle x_{i}+1,$
	$\displaystyle x_{i}^{(1)}$	$\displaystyle=$	$\displaystyle x_{i},$

for any Boolean variable $x_{i},i\in\mathbf{Z}_{N}$ .

Proof.

Note that

	$\displaystyle pr_{S}^{-1}(\{(b_{1},\cdots,b_{k})\})$
	$\displaystyle=\{(a_{0},\cdots,a_{N-1})\in\mathbf{F}_{2}^{N};(a_{s_{1}},\cdots,a_{s_{k}})=(b_{1},\cdots,b_{k})\}.$

Hence, denoting the complement $\mathbf{Z}_{N}\setminus S$ by $T=\{j_{1},\cdots,j_{N-k}\}$ , we see that

\displaystyle P(x_{0},\cdots,x_{N-1})=(x_{j_{1}}+\overline{x_{j_{1}}})\cdots(x_{j_{N-k}}+\overline{x_{j_{N-k}}})x_{s_{1}}^{(b_{1})}x_{s_{2}}^{(b_{2})}\cdots x_{s_{k}}^{(b_{k})}

by the algorithm explained in the subsection 4.1. Since $x_{j_{t}}+\overline{x_{j_{t}}}=1$ holds for any $t\in[1,N-k]$ , we finish the proof. ∎

We also need an equivalent form of the above proposition, where we change the set of indices $\mathbf{Z}_{N}$ to $\mathbf{Z}_{N,\pm}$ . Furthermore, since we have observed in the Table 4.5 that the Boolean variable ” $y=x+1$ ” is superior to the original $x$ for our study, we employ the negated variables as our basic building blocks. The following proposition is a direct consequence of Proposition 5.5:

Proposition 5.6.

Let $P=P(y_{\ell},\cdots,y_{g}):\mathbf{F}_{2}^{N}\rightarrow\mathbf{F}_{2}$ be a Boolean function with the following property: There exists a subset $S=\{s_{1},\cdots,s_{k}\}\subset\mathbf{Z}_{N,\pm}$ such that

\displaystyle P^{-1}(\{1\})=pr_{S}^{-1}(\{(b_{1},\cdots,b_{k})\})

holds for some $(b_{1},\cdots,b_{k})\in\mathbf{F}_{2}^{k}$ . Then we have

\displaystyle P(y_{\ell},\cdots,y_{g})=y_{s_{1}}^{(b_{1})}y_{s_{2}}^{(b_{2})}\cdots y_{s_{k}}^{(b_{k})},

where we put

	$\displaystyle y_{i}^{(0)}$	$\displaystyle=$	$\displaystyle y_{i},$
	$\displaystyle y_{i}^{(1)}$	$\displaystyle=$	$\displaystyle y_{i}+1,$

for any Boolean variable $y_{i},i\in\mathbf{Z}_{N,\pm}$ .

5.6 Ancestors of zero when $N=6$

Before we give a proof of Theorem 5.2, we examine the case when $N=6$ . This might help the reader to understand our proof for general cases.

The set $Par_{6}$ of parental pairs of zero has been found in Proposition 5.2 as follows:

\displaystyle Par_{6}=\{(0,0),(0,1),(-1,1),(-1,2),(-2,2),(-2,3)\}.

The figure below illustrates the ancestors of zero when $N=6$ :

Fig. 5.1. Ancestors of zero for $N=6$

Here are six families (1)-(6) of ancestors of 0, which are determined in Proposition 5.2 and Corollary 5.2. Each of six large circles represents the unit circle on the complex plane, and each member $k$ of $\mathbf{Z}_{6,\pm}$ are placed at the point $\exp(k\pi i/3)$ . The meanings of symbols in the figure are as follows:

(1) The numbers surrounding the unit circle specify the names of the elements in $\mathbf{Z}_{6,\pm}$ .
(2) Black dots represent the parental pairs of zero found in Proposition 5.2.
(3) Each of small blank circle signifies that the corresponding element does not appear in the ancestors.
(4) Each of circles having ” $\forall$ ” in its interior means that the corresponding element may or may not be present in the ancestors.

We should be careful about the rather exceptional case when $n=1$ , which is depicted as ”(6)”. Thus the $\mathbf{B}$ -ancestors of zero which correspond to the six figures are given by the following list:

\displaystyle\begin{array}[]{lll}\mbox{name}&\mbox{$\mathbf{B}$-ancestors of zero in }\mathbf{B}_{6,\pm}&\mbox{number of elements}\\ \hline\cr(1)&\{e_{[-2,3]}\}&1\\ (2)&pr_{[-2,2]}^{-1}(\{e_{[-2,2]}\})&2\\ (3)&pr_{[-1,2]}^{-1}(\{e_{[-1,2]}\})&4\\ (4)&pr_{[-1,1]}^{-1}(\{e_{[-1,1]}\})&8\\ (5)&pr_{[0,1]}^{-1}(\{e_{[0,1]}\})&16\\ (6)&\{(0,0,1,0,0,0)\}&1\\ Total&&32(=2^{6-1})\\ \end{array}

Table 5.2. Six families of the $\mathbf{B}$ -ancestors of zero for $N=6$

Let $S_{i}$ denote the subset of $\mathbf{B}_{6,\pm}$ which is specified in the $i$ -th row $(1\leq i\leq 6)$ , and let $f_{S_{i}}$ be the Boolean function which takes the value 1 (resp. 0) at every element of $S_{i}$ (resp. $\mathbf{B}_{6,\pm}\setminus S_{i})$ . Then it follows from Proposition 5.6 and Definition 5.11 that

$\displaystyle f_{S_{1}}$	$\displaystyle=$	$\displaystyle f_{[-2,3]}=(y_{-2}+1)y_{-1}y_{0}y_{1}y_{2}(y_{3}+1),$
$\displaystyle f_{S_{2}}$	$\displaystyle=$	$\displaystyle f_{[-2,2]}=(y_{-2}+1)y_{-1}y_{0}y_{1}(y_{2}+1),$
$\displaystyle f_{S_{3}}$	$\displaystyle=$	$\displaystyle f_{[-1,2]}=(y_{-1}+1)y_{0}y_{1}(y_{2}+1),$
$\displaystyle f_{S_{4}}$	$\displaystyle=$	$\displaystyle f_{[-1,1]}=(y_{-1}+1)y_{0}(y_{1}+1),$
$\displaystyle f_{S_{5}}$	$\displaystyle=$	$\displaystyle f_{[0,1]}=(y_{0}+1)(y_{1}+1),$
$\displaystyle f_{S_{6}}$	$\displaystyle=$	$\displaystyle f_{[0,0]}^{6}=(y_{0}+1)y_{-2}y_{-1}y_{1}y_{2}y_{3}.$

By summing these up, we have

\displaystyle Bav_{0}^{6}=\sum_{(a,b)\in Par_{6}\setminus\{(0,0)\}}f_{[a,b]}+f_{[0,0]}^{6},

which shows the validity of (5.6) of Theorem 5.2 when $N=6$ . Furthermore the total of the numbers of ancestors in the lines (1)-(6) is equal to 32, which is exactly the half of the number 64 of Boolean vectors in $\mathbf{B}_{6,\pm}$ . Therefore $Bav_{6}^{0}$ is balanced as is assured by Theorem 5.1.

5.7 Proof of Theorem 5.2

For any subset $U\subset\mathbf{B}_{N,\pm}$ , we denote by $P_{U}$ the polynomial function on $\mathbf{B}_{N,\pm}$ such that

\displaystyle P_{U}^{-1}(\{1\})=U.

Namely $P_{U}$ takes the value 1 on $U$ and the value 0 outside $U$ . Recall that we have $\mathbf{B}$ - $Anc_{N}(a,b)=pr_{[a,b]}^{-1}(\{e_{[a,b]}\})$ for any $(a,b)\in Par_{N}\setminus\{(0,0)\}$ by Corollary 5.2. This implies by Proposition 5.6 and definition 5.11 that

\displaystyle P_{\mathbf{B}-Anc_{N}(a,b)}=f_{[a,b]}.

The remaining parental pair $(0,0)\in Par_{N}$ corresponds to the one-element rhythm $(0)\in\mathbf{R}_{N}^{1}$ (see Remark 5.1). Since $RtoB((0))=(v_{i})_{i\in\mathbf{Z}_{N,\pm}}$ , where

\displaystyle v_{i}=\left\{\begin{array}[]{ll}1,&\mbox{ if }i=0,\\ 0,&\mbox{ if }i\neq 0,\\ \end{array}\right.

we have

\displaystyle P_{\mathbf{B}-Anc_{N}(0,0)}=f_{[0,0]}.

Thus we obtain the equality (5.8). This completes the proof of Theorem 5.2.

We check the validity of Theorem 5.2 by our computational results in Subsection 4.2.

Example 5.1. The case when $N=3$ : The equality (5.8) in Theorem 5.2 asserts that

\displaystyle Bav_{3}^{0}=\sum_{(a,b)\in Par_{3}\setminus\{(0,0)\}}f_{[a,b]}+f_{[0,0]}^{3}.

Recall that

\displaystyle Par_{3}=\{(0,0),(0,1),(-1,1)\}

by Proposition 5.2, and the corresponding polynomials $f_{[a,b]}$ , $(a,b)\in Par_{3}\setminus\{(0,0)\}$ and $f_{[0,0]}^{3}$ are defined in Definition 5.11 as follows:

$\displaystyle f_{[0,1]}$	$\displaystyle=$	$\displaystyle(y_{0}+1)(y_{1}+1),$
$\displaystyle f_{[-1,1]}$	$\displaystyle=$	$\displaystyle(y_{-1}+1)y_{0}(y_{1}+1),$
$\displaystyle f_{[0,0]}^{3}$	$\displaystyle=$	$\displaystyle(y_{0}+1)y_{-1}y_{1}.$

Hence we have

$\displaystyle Bav_{3}^{0}$	$\displaystyle=$	$\displaystyle(y_{0}+1)(y_{1}+1)+(y_{-1}+1)y_{0}(y_{1}+1)+(y_{0}+1)y_{-1}y_{1}$
	$\displaystyle=$	$\displaystyle(1+\underline{y_{0}}+y_{1}+\underline{y_{0}y_{1}})+y_{0}(\underline{1}+y_{-1}+\underline{y_{1}}+\underline{y_{-1}y_{1}})+y_{-1}(\underline{y_{0}}+1)y_{1}$
	$\displaystyle=$	$\displaystyle 1+y_{1}+y_{-1}y_{0}+y_{-1}y_{1},$
		$\displaystyle\hskip 85.35826pt(\mbox{by cancelling the underlined terms})$

and we see that the rightmost side coincides with Table 4.5 for $N=3$ .

Example 5.2. The case when $N=4$ : By Theorem 5.2, Proposition 5.2, and Definition 5.11, we can compute as follows:

$\displaystyle Bav_{4}^{0}$	$\displaystyle=$	$\displaystyle\sum_{(a,b)\in Par_{4}\setminus\{(0,0)\}}f_{[a,b]}+f_{[0,0]}^{4}$
	$\displaystyle=$	$\displaystyle f_{[0,1]}+f_{[-1,1]}+f_{[-1,2]}+f_{[0,0]}^{4}$
	$\displaystyle=$	$\displaystyle(y_{0}+1)(y_{1}+1)+(y_{-1}+1)y_{0}(y_{1}+1)+(y_{-1}+1)y_{0}y_{1}(y_{2}+1)$
		$\displaystyle\hskip 14.22636pt+(y_{0}+1)y_{-1}y_{1}y_{2}$
	$\displaystyle=$	$\displaystyle(1+\underline{y_{0}}+y_{1}+\underline{y_{0}y_{1}})+y_{0}(\underline{1}+y_{-1}+\underline{y_{1}}+\underline{y_{-1}y_{1}})$
		$\displaystyle+y_{0}y_{1}(1+\underline{y_{-1}}+y_{2}+\underline{y_{-1}y_{2}}))+(\underline{y_{0}}+1)y_{-1}y_{1}y_{2}$
	$\displaystyle=$	$\displaystyle 1+y_{1}+y_{-1}y_{0}+y_{0}y_{1}+y_{0}y_{1}y_{2}+y_{-1}y_{1}y_{2}.$
		$\displaystyle\hskip 85.35826pt(\mbox{by cancelling the underlined terms})$

The rightmost side coincides with Table 4.5 for $N=4$ .

5.8 Recurrence formula

Inspecting the shapes of $Bav_{N}^{0}$ found in Theorem 5.2, we are led naturally to the following:

Theorem 5.3.

When $N$ is even and $N=2m$ , we have

\displaystyle Bav_{2m}^{0}=Bav_{2m-1}^{0}+y_{-m+2}\cdots y_{-1}y_{1}\cdots y_{m-1}(y_{m}+1)(y_{0}+y_{-m+1}).

(5.17)

When $N$ is odd and $N=2m+1$ , we have

\displaystyle Bav_{2m+1}^{0}=Bav_{2m}^{0}+y_{-m+1}\cdots y_{-1}y_{1}\cdots y_{m-1}(y_{-m}+1)(y_{0}+y_{m}).

(5.18)

Proof.

It follows from Proposition 5.2 that

\displaystyle Par_{N}\subset Par_{N+1}

holds for any $N\geq 3$ . Hence we have only to consider their difference. We divide the proof into two parts according to the parity of $N$ .

1) The case when $N=2m\geq 4$ . It follows from Proposition 5.2 that

\displaystyle Par_{2m}\setminus Par_{2m-1}=\{[-m+1,m]\}.

Before we start our computation, for the convenience of the reader, we recall what members are in $\mathbf{Z}_{2m,\pm}$ or in $\mathbf{Z}_{2m-1,\pm}$ :

	$\displaystyle\mathbf{Z}_{2m,\pm}$	$\displaystyle=$	$\displaystyle\{x\in\mathbf{Z};-m+1\leq x\leq m\},$
	$\displaystyle\mathbf{Z}_{2m-1,\pm}$	$\displaystyle=$	$\displaystyle\{x\in\mathbf{Z};-m+1\leq x\leq m-1\}.$

Keeping in mind the fact that $-1=1$ in $\mathbf{F}_{2}$ , we can compute as follows:

			$\displaystyle Bav_{2m}^{0}-Bav_{2m-1}^{0}$
		$\displaystyle=$	$\displaystyle f_{[-m+1,m]}+f_{[0,0]}^{2m}-f_{[0,0]}^{2m-1}$
		$\displaystyle=$	$\displaystyle(y_{-m+1}+1)\left(\prod_{k=-m+2}^{m-1}y_{k}\right)(y_{m}+1)$
			$\displaystyle+\left((y_{0}+1)\prod_{k\in\mathbf{Z}_{2m,\pm}\setminus\{0\}}y_{k}-(y_{0}+1)\prod_{k\in\mathbf{Z}_{2m-1,\pm}\setminus\{0\}}y_{k}\right)$
		$\displaystyle=$	$\displaystyle(y_{-m+1}+1)\left(\prod_{k=-m+2}^{m-1}y_{k}\right)(y_{m}+1)$
			$\displaystyle\hskip 14.22636pt+(y_{0}+1)\left(\prod_{k\in\mathbf{Z}_{2m-1,\pm}\setminus\{0\}}y_{k}\right)(y_{m}-1)$
		$\displaystyle=$	$\displaystyle y_{-m+2}\cdots y_{-1}y_{1}\cdots y_{m-1}$
			$\displaystyle\times\left((y_{-m+1}+1)y_{0}(y_{m}+1)+y_{-m+1}(y_{0}+1)(y_{m}+1)\right)$
		$\displaystyle=$	$\displaystyle y_{-m+2}\cdots y_{-1}y_{1}\cdots y_{m-1}(y_{m}+1)$
			$\displaystyle\times\left((y_{-m+1}+1)y_{0}+y_{-m+1}(y_{0}+1)\right)$
		$\displaystyle=$	$\displaystyle y_{-m+2}\cdots y_{-1}y_{1}\cdots y_{m-1}(y_{m}+1)(y_{0}+y_{-m+1}).$

This shows the validity of (5.9).

2) The case when $N=2m+1\geq 5$ . It follows Proposition 5.2 that

\displaystyle Par_{2m+1}\setminus Par_{2m}=\{[-m,m]\}.

This time, the members of $\mathbf{Z}_{2m+1,\pm}$ and $\mathbf{Z}_{2m,\pm}$ are given by

	$\displaystyle\mathbf{Z}_{2m+1,\pm}$	$\displaystyle=$	$\displaystyle\{x\in\mathbf{Z};-m\leq x\leq m\},$
	$\displaystyle\mathbf{Z}_{2m,\pm}$	$\displaystyle=$	$\displaystyle\{x\in\mathbf{Z};-m+1\leq x\leq m\}.$

Hence we can compute as follows:

			$\displaystyle Bav_{2m+1}^{0}-Bav_{2m}^{0}$
		$\displaystyle=$	$\displaystyle f_{[-m,m]}+f_{[0,0]}^{2m+1}-f_{[0,0]}^{2m}$
		$\displaystyle=$	$\displaystyle(y_{-m}+1)\left(\prod_{k=-m+1}^{m-1}y_{k}\right)(y_{m}+1)$
			$\displaystyle+\left((y_{0}+1)\prod_{k\in\mathbf{Z}_{2m+1,\pm}\setminus\{0\}}y_{k}-(y_{0}+1)\prod_{k\in\mathbf{Z}_{2m,\pm}\setminus\{0\}}y_{k}\right)$
		$\displaystyle=$	$\displaystyle(y_{-m}+1)\left(\prod_{k=-m+1}^{m-1}y_{k}\right)(y_{m}+1)$
			$\displaystyle+(y_{0}+1)\left(\prod_{k\in\mathbf{Z}_{2m,\pm}\setminus\{0\}}y_{k}\right)(y_{-m}-1)$
		$\displaystyle=$	$\displaystyle y_{-m+1}\cdots y_{-1}y_{1}\cdots y_{m-1}$
			$\displaystyle\times\left((y_{-m}+1)y_{0}(y_{m}+1)+(y_{-m}+1)(y_{0}+1)y_{m}\right)$
		$\displaystyle=$	$\displaystyle y_{-m+1}\cdots y_{-1}y_{1}\cdots y_{m-1}(y_{-m}+1)$
			$\displaystyle\times\left(y_{0}(y_{m}+1)+(y_{0}+1)y_{m}\right)$
		$\displaystyle=$	$\displaystyle y_{-m+1}\cdots y_{-1}y_{1}\cdots y_{m-1}(y_{-m}+1)(y_{0}+y_{m}).$

This shows the validity of (5.10). This completes the proof. ∎

We have displayed in Table 4.5 the rhythm polynomials $Bav_{N}^{0}$ for $N=3,\cdots,6$ . We reexamine the results through Theorem 5.3.

Example 5.3. The case when $N=4$ . It follows from (5.9) with $m=2$ that

$\displaystyle Bav_{4}^{0}$	$\displaystyle=$	$\displaystyle Bav_{3}^{0}+y_{1}(y_{2}+1)(y_{0}+y_{-1})$
	$\displaystyle=$	$\displaystyle(1+y_{1}+y_{-1}y_{0}+\underline{y_{-1}y_{1}})+y_{1}(y_{-1}y_{2}+y_{0}y_{2}+\underline{y_{-1}}+y_{0})$
	$\displaystyle=$	$\displaystyle 1+y_{1}+y_{-1}y_{0}+y_{0}y_{1}+y_{-1}y_{1}y_{2}+y_{0}y_{1}y_{2},$
		$\displaystyle\hskip 85.35826pt(\mbox{by canceling the underlined terms})$

where the last polynomial coincides with the result in Table 4.5 for $N=4$ .

Example 5.4. The case when $N=5$ . It follows from (5.10) with $m=2$ that

$\displaystyle Bav_{5}^{0}$	$\displaystyle=$	$\displaystyle Bav_{4}^{0}+y_{-1}y_{1}(y_{-2}+1)(y_{0}+y_{2})$
	$\displaystyle=$	$\displaystyle(1+y_{1}+y_{-1}y_{0}+y_{0}y_{1}+\underline{y_{-1}y_{1}y_{2}}+y_{0}y_{1}y_{2})$
		$\displaystyle\hskip 56.9055pt+y_{-1}y_{1}(y_{-2}y_{0}+y_{-2}y_{2}+y_{0}+\underline{y_{2}})$
	$\displaystyle=$	$\displaystyle 1+y_{1}+y_{-1}y_{0}+y_{0}y_{1}+y_{-1}y_{0}y_{1}+y_{0}y_{1}y_{2}$
		$\displaystyle\hskip 56.9055pt+y_{-2}y_{-1}y_{0}y_{1}+y_{-2}y_{-1}y_{1}y_{2},$
		$\displaystyle\hskip 85.35826pt(\mbox{by canceling the underlined terms})$

which coincides with the result in Table 4.5 for $N=5$ .

References
$[1]$ Cusick, T. W., Stănică, Cryptographic Boolean Functions and Applications. Elsevier/Academic Press, Amsterdam, the Netherlands, 2009.
$[2]$ Hazama, F., Iterative method of construction for amooth rhythms. Journal of Mathematics and Music(2021), On-Line-First, 1-20,
https://doi.org/10.1080/17459737.2021.1924303
$[3]$ MacWilliams, F. J., Sloane, N. J. A., The Theory of Error-Correcting Codes. Elsevier/NorthHolland, Amsterdam, the Netherlands, 1977.
$[4]$ Whitesitt, J. E., Boolean Algebra and Its Application, Dover Bookds on Computer science, 2010.

Boolean polynomial expression of the discrete average on the space of rhythms

Abstract

0 Introduction

1 The discrete average on the space of rhythms 𝐑Nn\mathbf{R}_{N}^{n}

1.1 𝐙N\mathbf{Z}_{N}-interval and S1S^{1}-interval

1.2 𝐙N\mathbf{Z}_{N}-average and μN\mu_{N}-average

Proposition 1.1.

Proof.

Lemma 1.1.

Proposition 1.2.

Proof.

Corollary 1.1.

1.3 The space of rhythms and the discrete average transformation

Definition 1.1.

Definition 1.2.

Definition 1.3.

Definition 1.4.

Remark 1.1.

Proposition 1.3.

Proof.

2 From modulo-NN-world to the Boolean world

2.1 Quotient map 𝐑Nn→𝐑¯Nn\mathbf{R}_{N}^{n}\rightarrow\overline{\mathbf{R}}_{N}^{n} and its section

Definition 2.1.

Definition 2.2.

Definition 2.3.

Remark 2.1.

Remark 2.2.

2.2 Construction of a section of π\pi

Definition 2.4.

Remark 2.3.

Proposition 2.1.

Proof.

Proposition 2.2.

Proof.

Corollary 2.1.

Definition 2.5.

Remark 2.4.

Proposition 2.3.

Proof.

Proposition 2.4.

Remark 2.5.

2.3 From 𝐑¯Nn\overline{\mathbf{R}}_{N}^{n} to Boolean world via 𝐈Nn\mathbf{I}_{N}^{n}

Definition 2.6.

Definition 2.7.

Definition 2.8.

Proposition 2.5.

Proof.

Proposition 2.6.

Proof.

2.4 Counterpart of R​a​vRav on 𝐈Nn\mathbf{I}_{N}^{n}

Definition 2.9.

Proposition 2.7.

Proof.

Corollary 2.2.

Definition 2.10.

Proposition 2.8.

Proof.

Corollary 2.3.

Corollary 2.4.

Proof.

2.5 Counterpart of R​a​vRav on 𝐁Nn\mathbf{B}_{N}^{n}

Definition 2.11.

Lemma 2.1.

Proof.

Proposition 2.9.

3 Cyclicity of the components of the Boolean average

3.1 Boolean counterpart of the translation map t​rtr on 𝐑Nn\mathbf{R}_{N}^{n}

Proposition 3.1.

Proof.

Corollary 3.1.

Definition 3.1.

Proposition 3.2.

Proof.

Corollary 3.2.

Proof.

3.2 Cyclicity of the Boolean average

Theorem 3.1.

Proof.

Remark 3.1.

4 Polynomial expression of the Boolean average

1 The discrete average on the space of rhythms $\mathbf{R}_{N}^{n}$

1.1 $\mathbf{Z}_{N}$ -interval and $S^{1}$ -interval

1.2 $\mathbf{Z}_{N}$ -average and $\mu_{N}$ -average

2 From modulo- $N$ -world to the Boolean world

2.1 Quotient map $\mathbf{R}_{N}^{n}\rightarrow\overline{\mathbf{R}}_{N}^{n}$ and its section

2.2 Construction of a section of $\pi$

2.3 From $\overline{\mathbf{R}}_{N}^{n}$ to Boolean world via $\mathbf{I}_{N}^{n}$

2.4 Counterpart of $Rav$ on $\mathbf{I}_{N}^{n}$

2.5 Counterpart of $Rav$ on $\mathbf{B}_{N}^{n}$

3.1 Boolean counterpart of the translation map $tr$ on $\mathbf{R}_{N}^{n}$

5.2 Parental pair and ancestor of zero in $\mathbf{Z}_{N}$

5.3 Parental pair and ancestor of zero in $\mathbf{Z}_{N,\pm}$

5.4 Main theorem on the structure of the rhythm polynomial $Bav_{N}^{0}$

5.6 Ancestors of zero when $N=6$