Search

We show that there exist ordered orthogonal arrays, whose sizes deviate from the Rao bound by a factor that is polynomial in the parameters of the ordered orthogonal array. The proof is nonconstructive and based on a probabilistic method due to Kuperberg, Lovett and Peled. [ABSTRACT FROM AUTHOR]

A subset Y of the general linear group $\text{GL}(n,q)$ is called t -intersecting if $\text{rk}(x-y)\le n-t$ for all $x,y\in Y$ , or equivalently x and y agree pointwise on a t -dimensional subspace of $\mathbb{F}_q^n$ for all $x,y\in Y$. We show that, if n is sufficiently large compared to t , the size of every such t -intersecting set is at most that of the stabiliser of a basis of a t -dimensional subspace of $\mathbb{F}_q^n$. In case of equality, the characteristic vector of Y is a linear combination of the characteristic vectors of the cosets of these stabilisers. We also give similar results for subsets of $\text{GL}(n,q)$ that intersect not necessarily pointwise in t -dimensional subspaces of $\mathbb{F}_q^n$ and for cross-intersecting subsets of $\text{GL}(n,q)$. These results may be viewed as variants of the classical Erdős–Ko–Rado Theorem in extremal set theory and are q -analogs of corresponding results known for the symmetric group. Our methods are based on eigenvalue techniques to estimate the size of the largest independent sets in graphs and crucially involve the representation theory of $\text{GL}(n,q)$. [ABSTRACT FROM AUTHOR]

Planar functions are mappings from a finite field F q to itself with an extremal differential property. Such functions give rise to finite projective planes and other combinatorial objects. There is a subtle difference between the definitions of these functions depending on the parity of q and we consider the case that q is even. We classify polynomials of degree at most q 1 / 4 that induce planar functions on F q , by showing that such polynomials are precisely those in which the degree of every monomial is a power of two. As a corollary we obtain a complete classification of exceptional planar polynomials, namely polynomials over F q that induce planar functions on infinitely many extensions of F q. The proof strategy is to study the number of F q -rational points of an algebraic curve attached to a putative planar function. Our methods also give a simple proof of a new partial result for the classification of almost perfect nonlinear functions. [ABSTRACT FROM AUTHOR]

The Pursley-Sarwate criterion of a pair of finite complex-valued sequences measures the collective smallness of the aperiodic autocorrelations and the aperiodic cross-correlations of the two sequences. It is known that this quantity is always at least 1 with equality if and only if the sequence pair is a Golay pair. We exhibit pairs of complex-valued sequences whose entries have unit magnitude for which the Pursley-Sarwate criterion tends to 1 as the sequence length tends to infinity. Our constructions use different carefully chosen Chu sequences. [ABSTRACT FROM AUTHOR]

Abstract The largest Hamming distance between a Boolean function in n variables and the set of all affine Boolean functions in n variables is known as the covering radius ρ n of the [ 2 n , n + 1 ] Reed–Muller code. This number determines how well Boolean functions can be approximated by linear Boolean functions. We prove that lim n → ∞ ⁡ 2 n / 2 − ρ n / 2 n / 2 − 1 = 1 , which resolves a conjecture due to Patterson and Wiedemann from 1983. [ABSTRACT FROM AUTHOR]

The problem of constructing polynomials with all coefficients 1 or −1 and large merit factor (equivalently with small L 4 norm on the unit circle) arises naturally in complex analysis, condensed matter physics, and digital communications engineering. Most known constructions arise (sometimes in a subtle way) from difference sets, in particular from Paley and Singer difference sets. We consider the asymptotic merit factor of polynomials constructed from other difference sets, providing the first essentially new examples since 1991. In particular we prove a general theorem on the asymptotic merit factor of polynomials arising from cyclotomy, which includes results on Hall and Paley difference sets as special cases. In addition, we establish the asymptotic merit factor of polynomials derived from Gordon–Mills–Welch difference sets and Sidelnikov almost difference sets, proving two recent conjectures. [ABSTRACT FROM AUTHOR]

Three measures of pseudorandomness of finite binary sequences were introduced by Mauduit and Sárközy in 1997 and have been studied extensively since then: the normality measure, the well-distribution measure, and the correlation measure of order r. Our main result is that the correlation measure of order r for random binary sequences converges strongly, and so has a limiting distribution. This solves a problem due to Alon, Kohayakawa, Mauduit, Moreira, and Rödl. We also show that the best known lower bounds for the minimum values of the correlation measures are simple consequences of a celebrated result due to Welch concerning the maximum nontrivial scalar products over a set of vectors. [ABSTRACT FROM AUTHOR]

A hyperoval in the projective plane P 2 ( F q ) is a set of q + 2 points no three of which are collinear. Hyperovals have been studied extensively since the 1950s with the ultimate goal of establishing a complete classification. It is well known that hyperovals in P 2 ( F q ) are in one-to-one correspondence to polynomials with certain properties, called o-polynomials of F q . We classify o-polynomials of F q of degree less than 1 2 q 1 / 4 . As a corollary we obtain a complete classification of exceptional o-polynomials, namely polynomials over F q that are o-polynomials of infinitely many extensions of F q . [ABSTRACT FROM AUTHOR]

Let $A_n=(a_0,a_1,\ldots ,a_{n-1})$ be drawn uniformly at random from ${\{ }-1,+1{\} }^n$ and define\[M(A_n)=\max _{01}{\mathrm {}}.\]It is proved that $M(A_n)/\sqrt {n\log n}$ converges in probability to $\sqrt {2}$. This settles a problem first studied by Moon and Moser in the 1960s and proves in the affirmative a recent conjecture due to Alon, Litsyn, and Shpunt. It is also shown that the expectation of $M(A_n)/\sqrt {n\log n}$ tends to $\sqrt {2}$. [ABSTRACT FROM AUTHOR]

A binary sequence of length n is an n-tuple with elements in \-1,1\ and its peak sidelobe level is the largest absolute value of its aperiodic autocorrelations at nonzero shifts. A classical problem is to find binary sequences whose peak sidelobe level is small compared to the length of the sequence. Using known techniques from probabilistic combinatorics, this paper gives a construction for a binary sequence of length n with peak sidelobe level at most \sqrt2n\log (2n) for every n > 1. This improves the best known bound for the peak sidelobe level of a family of explicitly constructed binary sequences, which arises for the family of m-sequences. By numerical analysis, it is argued that the peak sidelobe level of the constructed sequences grows in fact like order \sqrtn\log\log n and, therefore, grows strictly more slowly than the peak sidelobe level of a typical binary sequence. [ABSTRACT FROM AUTHOR]

For integer r satisfying 0\leq r\leq p-2, a sequence family \Omega_r of polyphase sequences of prime period p, size (p-2)p^r, and maximum correlation at most 2+(r+1)\sqrtp is presented. The sequence families are nested, that is, \Omega_r is contained in \Omegar+1, which provides design flexibility with respect to family size and maximum correlation. The sequences in \Omega_r are derived from a combination of multiplicative and additive characters of a prime field. Estimates on hybrid character sums are then used to bound the maximum correlation. This construction generalizes \Omega_0, which was previously proposed by Scholtz and Welch. Sequence family \Omega_2 is closely related to a recent design by Wang and Gong, who bounded its maximum correlation using methods from representation theory and asked for a more direct proof of this bound. Such a proof is given here and an improvement of the bound is provided. [ABSTRACT FROM AUTHOR]

Abstract: Let be the set of symmetric bilinear forms on an m-dimensional vector space over , where q is a power of two. A subset Y of is called an -set if the difference of every two distinct elements in Y has rank at least d. Such objects are closely related to certain families of codes over Galois rings of characteristic four. An upper bound on the size of -sets is derived, and in certain cases, the rank distance distribution of an -set is explicitly given. Constructions of -sets are provided for all possible values of m and d. [ABSTRACT FROM AUTHOR]

In this paper, 74-valued quadratic forms defined on a vector space over GF(2) are studied. A classification of such forms is established, distinguishing Z4-valued quadratic forms only by their rank and whether the associated bilinear form is alternating. This result is used to compute the distribution of certain exponential sums, which occur frequently in the analysis of quaternary codes and quaternary sequence sets. The concept is applied as follows. When t = 0 or m is odd, the correlation distribution of family S (t), consisting of quaternary sequences of length 2m - 1, is established. Then, motivated by practical considerations, a subset S* (t) of family S (t) is defined, and the correlation distribution of family S* (t) is given for odd and even m. [ABSTRACT FROM AUTHOR]

A constant-amplitude code is a code that reduces the peak-to-average power ratio (PAPR) in multicode code-division multiple access (MC-CDMA) systems to the favorable value 1. In this paper, quaternary constant-amplitude codes (codes over Z4) of length 2m with error-correction capabilities are studied. These codes exist for every positive integer m, while binary constant-amplitude codes cannot exist if m is odd. Every word of such a code corresponds to a function from the binary m-tuples to Z4 having the bent property, i.e., its Fourier transform has magnitudes 2m/2. Several constructions of such functions are presented, which are exploited in connection with algebraic codes over Z4 (in particular quaternary Reed-Muller, Kerdock, and Delsarte-Goethals codes) to construct families of quaternary constant-amplitude codes. Mappings from binary to quaternary constant-amplitude codes are presented as well. [ABSTRACT FROM AUTHOR]

The peak-to-mean envelope power ratio (PMEPR) of a code employed in orthogonal frequency-division multiplexing (OFDM) systems can be reduced by permuting its coordinates and by rotating each coordinate by a fixed phase shift. Motivated by some previous designs of phase shifts using suboptimal methods, the following question is considered in this paper. For a given binary code, how much PMEPR reduction can be achieved when the phase shifts are taken from a 2h-ary phase-shift keying (2h-PSK) constellation? A lower bound on the achievable PMEPR is established, which is related to the covering radius of the binary code. Generally speaking, the achievable region of the PMEPR shrinks as the covering radius of the binary code decreases. The bound is then applied to some well understood codes, including nonredundant BPSK signaling, BCH codes and their duals, Reed-Muller codes, and convolutional codes. It is demonstrated that most (presumably not optimal) phase-shift designs from the literature attain or approach our bound. [ABSTRACT FROM AUTHOR]

The use of error-correcting codes for tight control of the peak-to-mean envelope power ratio (PMEPR) in orthogonal frequency-division multiplexing (OFDM) transmission is considered in this correspondence. By generalizing a result by Paterson, it is shown that each q-phase (q is even) sequence of length 2m lies in a complementary set of size 2k+1, where k is a nonnegative integer that can be easily determined from the generalized Boolean function associated with the sequence. For small k this result provides a reasonably tight bound for the PMEPR of q-phase sequences of length 2m. A new 2 h-ary generalization of the classical Reed-Muller code is then used together with the result on complementary sets to derive flexible OFDM coding schemes with low PMEPR. These codes include the codes developed by Davis and Jedwab as a special case. In certain situations the codes in the present correspondence are similar to Paterson's code constructions and often outperform them. [ABSTRACT FROM AUTHOR]

Golay sequences are well suited for use as codewords in orthogonal frequency-division multiplexing (OFDM), since their peak-to-mean envelope power ratio (PMEPR) in q-ary phase-shift keying (PSK) modulation is at most 2. It is known that a family of polyphase Golay sequences of length 2m organizes in m!/2 cosets of a q-ary generalization of the first-order Reed-Muller code, RMq (1, m). In this paper, a more general construction technique for cosets of RMq(1, m) with low PMEPR is established. These cosets contain so-called near-complementary sequences. The application of this theory is then illustrated by providing some construction examples. First, it is shown that the m!/2 cosets of RMq(1, m) comprised of Golay sequences just arise as a special case. Second, further families of cosets of RMq(1, m) with maximum PMEPR between 2 and 4 are presented, showing that some previously unexplained phenomena can now he understood within a unified framework. A lower bound on the PMEPR of cosets of RMq(1, m) is proved us well, and it is demonstrated that the upper bound on the PMEPR is tight in many cases. Finally, it is shown that all upper bounds on the PMEPR of cosets of RMq(1, m) also hold for the peak-to-average power ratio (PAPR) under the Walsh-Hadamard transform (WHT). [ABSTRACT FROM AUTHOR]

Abstract: We give a solution to an extremal problem for polynomials, which asks for complex numbers of unit magnitude that minimise the largest supremum norm on the unit circle for all polynomials of degree n whose k-th coefficient is either or . [Copyright &y& Elsevier]

We consider a generalisation of a conjecture by Patterson and Wiedemann from 1983 on the Hamming distance of a function from F q n to F q to the set of affine functions from F q n to F q. We prove the conjecture for each q such that the characteristic of F q lies in a subset of the primes with density 1 and we prove the conjecture for all q by assuming the generalised Riemann hypothesis. Roughly speaking, we show the existence of functions for which the distance to the affine functions is maximised when n tends to infinity. This also determines the asymptotic behaviour of the covering radius of the [ q n , n + 1 ] Reed-Muller code over F q and so answers a question raised by Leducq in 2013. Our results extend the case q = 2 , which was recently proved by the author and which corresponds to the original conjecture by Patterson and Wiedemann. Our proof combines evaluations of Gauss sums in the semiprimitive case, probabilistic arguments, and methods from discrepancy theory. [ABSTRACT FROM AUTHOR]

Abstract: Littlewood asked how small the ratio (where denotes the norm on the unit circle) can be for polynomials having all coefficients in , as the degree tends to infinity. Since 1988, the least known asymptotic value of this ratio has been , which was conjectured to be minimum. We disprove this conjecture by showing that there is a sequence of such polynomials, derived from the Fekete polynomials, for which the limit of this ratio is less than . [Copyright &y& Elsevier]

Abstract: The identification of binary sequences with large merit factor (small mean-squared aperiodic autocorrelation) is an old problem of complex analysis and combinatorial optimization, with practical importance in digital communications engineering and condensed matter physics. We establish the asymptotic merit factor of several families of binary sequences and thereby prove various conjectures, explain numerical evidence presented by other authors, and bring together within a single framework results previously appearing in scattered form. We exhibit, for the first time, families of skew-symmetric sequences whose asymptotic merit factor is as large as the best known value (an algebraic number greater than 6.34) for all binary sequences; this is interesting in light of Golayʼs conjecture that the subclass of skew-symmetric sequences has asymptotically optimal merit factor. Our methods combine Fourier analysis, estimation of character sums, and estimation of the number of lattice points in polyhedra. [Copyright &y& Elsevier]

An editorial is presented on climate geoengineering approaches to limit the global temperature rise. Topics discussed include two types of geoengineering to reduce greenhouse gas emissions including carbon dioxide removal from the atmosphere, and solar radiation management to cool the Earth; need for a strategic approach to climate geoengineering policies to prevent other serious risks of geoengineering; and frameworks on the use of geoengineering created by Convention on Biological Diversity.

A 3-phase Barker array is a matrix of third roots of unity for which all out-of-phase aperiodic autocorrelations have magnitude 0 or 1. The only known truly two-dimensional 3-phase Barker arrays have size 2 × 2 or 3 × 3. We use a mixture of combinatorial arguments and algebraic number theory to establish severe restrictions on the size of a 3-phase Barker array when at least one of its dimensions is divisible by 3. In particular, there exists a double-exponentially growing arithmetic function T such that no 3-phase Barker array of size [ABSTRACT FROM AUTHOR]