BZPEER

preprint2023arXiv

The Covering Radius of the Third-Order Reed-Muller Code RM(3,7) is 20

We prove the covering radius of the third-order Reed-Muller code RM(3,7) is 20, which was previously known to be between 20 and 23 (inclusive). The covering radius of RM(3, 7) is the maximum third-order nonlinearity among all 7-variable Boolean functions. It was known that there exist 7-variable Boolean functions with third-order nonlinearity 20. We prove the third-order nonlinearity cannot achieve 21. According to the classification of the quotient space of RM(6,6)/RM(3,6), we classify all 7-variable Boolean functions into 66 types. Firstly, we prove 62 types (among 66) cannot have third-order nonlinearity 21; Secondly, we prove function of the remaining 4 types can be transformed into a type (6, 10) function, if its third-order nonlinearity is 21; Finally, we transform type (6, 10) functions into a specific form, and prove the functions in that form cannot achieve third-order nonlinearity 21 (with the assistance of computers). By the way, we prove that the affine transformation group over any finite field can be generated by two elements.

preprint2022arXiv

Isometries and MacWilliams Extension Property for Weighted Poset Metric

Let $\mathbf{H}$ be the cartesian product of a family of left modules over a ring $S$ , indexed by a finite set $Ω$ . We are concerned with the $(\mathbf{P},ω)$ -weight on $\mathbf{H}$ , where $\mathbf{P}=(Ω,\preccurlyeq_{\mathbf{P}})$ is a poset and $ω:Ω\longrightarrow\mathbb{R}^{+}$ is a weight function. We characterize the group of $(\mathbf{P},ω)$ -weight isometries of $\mathbf{H}$ , and give a canonical decomposition for semi-simple subcodes of $\mathbf{H}$ when $\mathbf{P}$ is hierarchical. We then study the MacWilliams extension property (MEP) for $(\mathbf{P},ω)$ -weight. We show that the MEP implies the unique decomposition property (UDP) of $(\mathbf{P},ω)$ , which further implies that $\mathbf{P}$ is hierarchical if $ω$ is identically $1$ . For the case that either $\mathbf{P}$ is hierarchical or $ω$ is identically $1$ , we show that the MEP for $(\mathbf{P},ω)$ -weight can be characterized in terms of the MEP for Hamming weight, and give necessary and sufficient conditions for $\mathbf{H}$ to satisfy the MEP for $(\mathbf{P},ω)$ -weight when $S$ is an Artinian simple ring (either finite or infinite). When $S$ is a finite field, in the context of $(\mathbf{P},ω)$ -weight, we compare the MEP with other coding theoretic properties including the MacWilliams identity, Fourier-reflexivity of partitions and the UDP, and show that the MEP is strictly stronger than all the rest among them.

preprint2022arXiv

Minimal Binary Linear Codes from Vectorial Boolean Functions

Recently, much progress has been made to construct minimal linear codes due to their preference in secret sharing schemes and secure two-party computation. In this paper, we put forward a new method to construct minimal linear codes by using vectorial Boolean functions. Firstly, we give a necessary and sufficient condition for a generic class of linear codes from vectorial Boolean functions to be minimal. Based on that, we derive some new three-weight minimal linear codes and determine their weight distributions. Secondly, we obtain a necessary and sufficient condition for another generic class of linear codes from vectorial Boolean functions to be minimal and to be violated the AB condition. As a result, we get three infinite families of minimal linear codes violating the AB condition. To the best of our knowledge, this is the first time that minimal liner codes are constructed from vectorial Boolean functions. Compared with other known ones, in general the minimal liner codes obtained in this paper have higher dimensions.

preprint2022arXiv

Reflexivity of Partitions Induced by Weighted Poset Metric and Combinatorial Metric

Let $\mathbf{H}$ be the Cartesian product of a family of finite abelian groups. Via a polynomial approach, we give sufficient conditions for a partition of $\mathbf{H}$ induced by weighted poset metric to be reflexive, which also become necessary for some special cases. Moreover, by examining the roots of the Krawtchouk polynomials, we establish non-reflexive partitions of $\mathbf{H}$ induced by combinatorial metric. When $\mathbf{H}$ is a vector space over a finite field $\mathbb{F}$ , we consider the property of admitting MacWilliams identity (PAMI) and the MacWilliams extension property (MEP) for partitions of $\mathbf{H}$ . With some invariance assumptions, we show that two partitions of $\mathbf{H}$ admit MacWilliams identity if and only if they are mutually dual and reflexive, and any partition of $\mathbf{H}$ satisfying the MEP is in fact an orbit partition induced by some subgroup of $\Aut_{\mathbb{F}}(\mathbf{H})$, which is necessarily reflexive. As an application of the aforementioned results, we establish partitions of $\mathbf{H}$ induced by combinatorial metric that do not satisfy the MEP, which further enable us to provide counter-examples to a conjecture proposed by Pinheiro, Machado and Firer in \cite{39}.

preprint2021arXiv

Coherence Scaling of Noisy Second-Order Scale-Free Consensus Networks

A striking discovery in the field of network science is that the majority of real networked systems have some universal structural properties. In generally, they are simultaneously sparse, scale-free, small-world, and loopy. In this paper, we investigate the second-order consensus of dynamic networks with such universal structures subject to white noise at vertices. We focus on the network coherence $H_{\rm SO}$ characterized in terms of the $\mathcal{H}_2$ -norm of the vertex systems, which measures the mean deviation of vertex states from their average value. We first study numerically the coherence of some representative real-world networks. We find that their coherence $H_{\rm SO}$ scales sublinearly with the vertex number $N$ . We then study analytically $H_{\rm SO}$ for a class of iteratively growing networks -- pseudofractal scale-free webs (PSFWs), and obtain an exact solution to $H_{\rm SO}$ , which also increases sublinearly in $N$ , with an exponent much smaller than 1. To explain the reasons for this sublinear behavior, we finally study $H_{\rm SO}$ for Sierpinśki gaskets, for which $H_{\rm SO}$ grows superlinearly in $N$ , with a power exponent much larger than 1. Sierpinśki gaskets have the same number of vertices and edges as the PSFWs, but do not display the scale-free and small-world properties. We thus conclude that the scale-free and small-world, and loopy topologies are jointly responsible for the observed sublinear scaling of $H_{\rm SO}$ .

preprint2021arXiv

Constructing new APN functions through relative trace functions

In 2020, Budaghyan, Helleseth and Kaleyski [IEEE TIT 66(11): 7081-7087, 2020] considered an infinite family of quadrinomials over $\mathbb{F}_{2^{n}}$ of the form $x^3+a(x^{2^s+1})^{2^k}+bx^{3\cdot 2^m}+c(x^{2^{s+m}+2^m})^{2^k}$ , where $n=2m$ with $m$ odd. They proved that such kind of quadrinomials can provide new almost perfect nonlinear (APN) functions when $\gcd(3,m)=1$ , $k=0$ , and $(s,a,b,c)=(m-2,ω, ω^2,1)$ or $((m-2)^{-1}~{\rm mod}~n,ω, ω^2,1)$ in which $ω\in\mathbb{F}_4\setminus \mathbb{F}_2$ . By taking $a=ω$ and $b=c=ω^2$ , we observe that such kind of quadrinomials can be rewritten as $a {\rm Tr}^{n}_{m}(bx^3)+a^q{\rm Tr}^{n}_{m}(cx^{2^s+1})$ , where $q=2^m$ and ${\rm Tr}^n_{m}(x)=x+x^{2^m}$ for $n=2m$ . Inspired by the quadrinomials and our observation, in this paper we study a class of functions with the form $f(x)=a{\rm Tr}^{n}_{m}(F(x))+a^q{\rm Tr}^{n}_{m}(G(x))$ and determine the APN-ness of this new kind of functions, where $a \in \mathbb{F}_{2^n}$ such that $a+a^q\neq 0$ , and both $F$ and $G$ are quadratic functions over $\mathbb{F}_{2^n}$ . We first obtain a characterization of the conditions for $f(x)$ such that $f(x)$ is an APN function. With the help of this characterization, we obtain an infinite family of APN functions for $n=2m$ with $m$ being an odd positive integer: $f(x)=a{\rm Tr}^{n}_{m}(bx^3)+a^q{\rm Tr}^{n}_{m}(b^3x^9)$ , where $a\in \mathbb{F}_{2^n}$ such that $a+a^q\neq 0$ and $b$ is a non-cube in $\mathbb{F}_{2^n}$ .

preprint2014arXiv

On the Minimum Decoding Delay of Balanced Complex Orthogonal Design

Complex orthogonal design (COD) with parameter $[p, n, k]$ is a combinatorial design used in space-time block codes (STBCs). For STBC, $n$ is the number of antennas, $k/p$ is the rate, and $p$ is the decoding delay. A class of rate $1/2$ COD called balanced complex orthogonal design (BCOD) has been proposed by Adams et al., and they constructed BCODs with rate $k/p = 1/2$ and decoding delay $p = 2^m$ for $n=2m$ . Furthermore, they prove that the constructions have optimal decoding delay when $m$ is congruent to $1$ , $2$ , or $3$ module $4$ . They conjecture that for the case $m \equiv 0 \pmod 4$ , $2^m$ is also a lower bound of $p$ . In this paper, we prove this conjecture.

preprint2012arXiv

A Note on "On the Construction of Boolean Functions with Optimal Algebraic Immunity"

In this note, we go further on the "basis exchange" idea presented in \cite{LiNa1} by using Mobious inversion. We show that the matrix $S_1(f)S_0(f)^{-1}$ has a nice form when $f$ is chosen to be the majority function, where $S_1(f)$ is the matrix with row vectors $\upsilon_k(α)$ for all $α\in 1_f$ and $S_0(f)=S_1(f\oplus1)$ . And an exact counting for Boolean functions with maximum algebraic immunity by exchanging one point in on-set with one point in off-set of the majority function is given. Furthermore, we present a necessary condition according to weight distribution for Boolean functions to achieve algebraic immunity not less than a given number.

preprint2012arXiv

Capacity Factors of a Point-to-point Network

In this paper, we investigate some properties on capacity factors, which were proposed to investigate the link failure problem from network coding. A capacity factor (CF) of a network is an edge set, deleting which will cause the maximum flow to decrease while deleting any proper subset will not. Generally, a $k$ -CF is a minimal (not minimum) edge set which will cause the network maximum flow decrease by $k$ . Under point to point acyclic scenario, we characterize all the edges which are contained in some CF, and propose an efficient algorithm to classify. And we show that all edges on some $s$ - $t$ path in an acyclic point-to-point acyclic network are contained in some 2-CF. We also study some other properties of CF of point to point network, and a simple relationship with CF in multicast network. On the other hand, some computational hardness results relating to capacity factors are obtained. We prove that deciding whether there is a capacity factor of a cyclic network with size not less a given number is NP-complete, and the time complexity of calculating the capacity rank is lowered bounded by solving the maximal flow. Besides that, we propose the analogous definition of CF on vertices and show it captures edge capacity factors as a special case.

preprint2012arXiv

Complex Orthogonal Designs with Forbidden $2 \times 2$ Submatrices

Complex orthogonal designs (CODs) are used to construct space-time block codes. COD $\mathcal{O}_z$ with parameter $[p, n, k]$ is a $p \times n$ matrix, where nonzero entries are filled by $\pm z_i$ or $\pm z^*_i$ , $i = 1, 2,..., k$ , such that $\mathcal{O}^H_z \mathcal{O}_z = (|z_1|^2+|z_2|^2+...+|z_k|^2)I_{n \times n}$ . Define $\mathcal{O}_z$ a first type COD if and only if $\mathcal{O}_z$ does not contain submatrix {\pm z_j & 0; \ 0 & \pm z^*_j} $or$ {\pm z^*_j & 0; \ 0 & \pm z_j} $. It is already known that, all CODs with maximal rate, i.e., maximal$ k/p $, are of the first type. In this paper, we determine all achievable parameters$ [p, n, k] $of first type COD, as well as all their possible structures. The existence of parameters is proved by explicit-form constructions. New CODs with parameters$ [p,n,k]=[\binom{n}{w-1}+\binom{n}{w+1}, n, \binom{n}{w}], $for$ 0 \le w \le n$, are constructed, which demonstrate the possibility of sacrificing code rate to reduce decoding delay. It's worth mentioning that all maximal rate, minimal delay CODs are contained in our constructions, and their uniqueness under equivalence operation is proved.

preprint2012arXiv

On $2k$ -Variable Symmetric Boolean Functions with Maximum Algebraic Immunity $k$

Algebraic immunity of Boolean function $f$ is defined as the minimal degree of a nonzero $g$ such that $fg=0$ or $(f+1)g=0$ . Given a positive even integer $n$ , it is found that the weight distribution of any $n$ -variable symmetric Boolean function with maximum algebraic immunity $\frac{n}{2}$ is determined by the binary expansion of $n$ . Based on the foregoing, all $n$ -variable symmetric Boolean functions with maximum algebraic immunity are constructed. The amount is $(2\wt(n)+1)2^{\lfloor \log_2 n \rfloor}$

preprint2011arXiv

Constructing and Counting Even-Variable Symmetric Boolean Functions with Algebraic Immunity not Less Than $d$

In this paper, we explicitly construct a large class of symmetric Boolean functions on $2k$ variables with algebraic immunity not less than $d$ , where integer $k$ is given arbitrarily and $d$ is a given suffix of $k$ in binary representation. If let $d = k$ , our constructed functions achieve the maximum algebraic immunity. Remarkably, $2^{\lfloor \log_2{k} \rfloor + 2}$ symmetric Boolean functions on $2k$ variables with maximum algebraic immunity are constructed, which is much more than the previous constructions. Based on our construction, a lower bound of symmetric Boolean functions with algebraic immunity not less than $d$ is derived, which is $2^{\lfloor \log_2{d} \rfloor + 2(k-d+1)}$ . As far as we know, this is the first lower bound of this kind.

preprint2011arXiv

On the nonexistence of $[\binom{2m}{m-1}, 2m, \binom{2m-1}{m-1}]$ , $m$ odd, complex orthogonal design

Complex orthogonal designs (CODs) are used to construct space-time block codes. COD $\mathcal{O}_z$ with parameter $[p, n, k]$ is a $p\times n$ matrix, where nonzero entries are filled by $\pm z_i$ or $\pm z^*_i$ , $i = 1, 2,..., k$ , such that $\mathcal{O}^H_z \mathcal{O}_z = (|z_1|^2+|z_2|^2+...+|z_k|^2)I_{n \times n}$ . Adams et al. in "The final case of the decoding delay problem for maximum rate complex orthogonal designs," IEEE Trans. Inf. Theory, vol. 56, no. 1, pp. 103-122, Jan. 2010, first proved the nonexistence of $[\binom{2m}{m-1}, 2m, \binom{2m-1}{m-1}]$ , $m$ odd, COD. Combining with the previous result that decoding delay should be an integer multiple of $\binom{2m}{m-1}$ , they solved the final case $n \equiv 2 \pmod 4$ of the decoding delay problem for maximum rate complex orthogonal designs. In this paper, we give another proof of the nonexistence of COD with parameter $[\binom{2m}{m-1}, 2m, \binom{2m-1}{m-1}]$ , $m$ odd. Our new proof is based on the uniqueness of $[\binom{2m}{m-1}, 2m-1, \binom{2m-1}{m-1}]$ under equivalence operation, where an explicit-form representation is proposed to help the proof. Then, by proving it's impossible to add an extra orthogonal column on COD $[\binom{2m}{m-1}, 2m-1, \binom{2m-1}{m-1}]$ when $m$ is odd, we complete the proof of the nonexistence of COD $[\binom{2m}{m-1}, 2m, \binom{2m-1}{m-1}]$ .

Haibin Kan

Research overview

Is this your work?

13 publications

The Covering Radius of the Third-Order Reed-Muller Code RM(3,7) is 20

Isometries and MacWilliams Extension Property for Weighted Poset Metric

Minimal Binary Linear Codes from Vectorial Boolean Functions

Reflexivity of Partitions Induced by Weighted Poset Metric and Combinatorial Metric

Coherence Scaling of Noisy Second-Order Scale-Free Consensus Networks

Constructing new APN functions through relative trace functions

On the Minimum Decoding Delay of Balanced Complex Orthogonal Design

A Note on "On the Construction of Boolean Functions with Optimal Algebraic Immunity"

Capacity Factors of a Point-to-point Network

Complex Orthogonal Designs with Forbidden $2 \times 2$ Submatrices

On $2k$ -Variable Symmetric Boolean Functions with Maximum Algebraic Immunity $k$

Constructing and Counting Even-Variable Symmetric Boolean Functions with Algebraic Immunity not Less Than $d$

On the nonexistence of $[\binom{2m}{m-1}, 2m, \binom{2m-1}{m-1}]$ , $m$ odd, complex orthogonal design

See the researcher in context

Building this map preview

Haibin Kan

Research overview

Is this your work?

13 publications

The Covering Radius of the Third-Order Reed-Muller Code RM(3,7) is 20

Isometries and MacWilliams Extension Property for Weighted Poset Metric

Minimal Binary Linear Codes from Vectorial Boolean Functions

Reflexivity of Partitions Induced by Weighted Poset Metric and Combinatorial Metric

Coherence Scaling of Noisy Second-Order Scale-Free Consensus Networks

Constructing new APN functions through relative trace functions

On the Minimum Decoding Delay of Balanced Complex Orthogonal Design

A Note on "On the Construction of Boolean Functions with Optimal Algebraic Immunity"

Capacity Factors of a Point-to-point Network

Complex Orthogonal Designs with Forbidden 2×22 \times 22×2 Submatrices

On 2k2k2k-Variable Symmetric Boolean Functions with Maximum Algebraic Immunity kkk

Constructing and Counting Even-Variable Symmetric Boolean Functions with Algebraic Immunity not Less Than ddd

On the nonexistence of [(2mm−1),2m,(2m−1m−1)][\binom{2m}{m-1}, 2m, \binom{2m-1}{m-1}][(m−12m​),2m,(m−12m−1​)], mmm odd, complex orthogonal design

See the researcher in context

Building this map preview

Complex Orthogonal Designs with Forbidden $2 \times 2$ Submatrices

On $2k$ -Variable Symmetric Boolean Functions with Maximum Algebraic Immunity $k$

Constructing and Counting Even-Variable Symmetric Boolean Functions with Algebraic Immunity not Less Than $d$

On the nonexistence of $[\binom{2m}{m-1}, 2m, \binom{2m-1}{m-1}]$ , $m$ odd, complex orthogonal design