Source author record

Jonathan Jedwab

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Information Theory math.IT math.NT Biomolecules Data Structures and Algorithms math.RA

Catalog footprint

Research overview

13works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A group-based structure for perfect sequence covering arrays

An $(n,k)$ -perfect sequence covering array with multiplicity $λ$ , denoted PSCA $(n,k,λ)$ , is a multiset whose elements are permutations of the sequence $(1,2, \dots, n)$ and which collectively contain each ordered length $k$ subsequence exactly $λ$ times. The primary objective is to determine for each pair $(n,k)$ the smallest value of $λ$ , denoted $g(n,k)$ , for which a PSCA $(n,k,λ)$ exists; and more generally, the complete set of values $λ$ for which a PSCA $(n,k,λ)$ exists. Yuster recently determined the first known value of $g(n,k)$ greater than 1, namely $g(5,3)=2$ , and suggested that finding other such values would be challenging. We show that $g(6,3)=g(7,3)=2$ , using a recursive search method inspired by an old algorithm due to Mathon. We then impose a group-based structure on a perfect sequence covering array by restricting it to be a union of distinct cosets of a prescribed nontrivial subgroup of the symmetric group $S_n$ . This allows us to determine the new results that $g(7,4)=2$ and $g(7,5) \in \{2,3,4\}$ and $g(8,3) \in \{2,3\}$ and $g(9,3) \in \{2,3,4\}$ . We also show that, for each $(n,k) \in \{ (5,3), (6,3), (7,3), (7,4) \}$ , there exists a PSCA $(n,k,λ)$ if and only if $λ\ge 2$ ; and that there exists a PSCA $(8,3,λ)$ if and only if $λ\ge g(8,3)$ .

preprint2020arXiv

An infinite class of unsaturated rooted trees corresponding to designable RNA secondary structures

An RNA secondary structure is designable if there is an RNA sequence which can attain its maximum number of base pairs only by adopting that structure. The combinatorial RNA design problem, introduced by Haleš et al. in 2016, is to determine whether or not a given RNA secondary structure is designable. Haleš et al. identified certain classes of designable and non-designable secondary structures by reference to their corresponding rooted trees. We introduce an infinite class of rooted trees containing unpaired nucleotides at the greatest depth, and prove constructively that their corresponding secondary structures are designable. This complements previous results for the combinatorial RNA design problem.

preprint2020arXiv

Which graphs occur as $γ$ -graphs?

The $γ$ -graph of a graph $G$ is the graph whose vertices are labelled by the minimum dominating sets of $G$ , in which two vertices are adjacent when their corresponding minimum dominating sets (each of size $γ(G)$ ) intersect in a set of size $γ(G)-1$ . We extend the notion of a $γ$ -graph from distance-1-domination to distance- $d$ -domination, and ask which graphs $H$ occur as $γ$ -graphs for a given value of~ $d \ge 1$ . We show that, for all $d$ , the answer depends only on whether the vertices of $H$ admit a labelling consistent with the adjacency condition for a conventional $γ$ -graph. This result relies on an explicit construction for a graph having an arbitrary prescribed set of minimum distance- $d$ -dominating sets. We then completely determine the graphs that admit such a labelling among the wheel graphs, the fan graphs, and the graphs on at most six vertices. We connect the question of whether a graph admits such a labelling with previous work on induced subgraphs of Johnson graphs.

preprint2018arXiv

A new structure for difference matrices over abelian $p$ -groups

A difference matrix over a group is a discrete structure that is intimately related to many other combinatorial designs, including mutually orthogonal Latin squares, orthogonal arrays, and transversal designs. Interest in constructing difference matrices over $2$ -groups has been renewed by the recent discovery that these matrices can be used to construct large linking systems of difference sets, which in turn provide examples of systems of linked symmetric designs and association schemes. We survey the main constructive and nonexistence results for difference matrices, beginning with a classical construction based on the properties of a finite field. We then introduce the concept of a contracted difference matrix, which generates a much larger difference matrix. We show that several of the main constructive results for difference matrices over abelian $p$ -groups can be substantially simplified and extended using contracted difference matrices. In particular, we obtain new linking systems of difference sets of size $7$ in infinite families of abelian $2$ -groups, whereas previously the largest known size was $3$ .

preprint2016arXiv

An infinite family of strongly unextendible mutually unbiased bases in $\mathbb{C}^{2^{2h}}$

A set of $b$ mutually unbiased bases (MUBs) in $\mathbb{C}^d$ (for $d > 1$ ) comprises $bd$ vectors in $\mathbb{C}^d$ , partitioned into $b$ orthogonal bases for $\mathbb{C}^d$ such that the pairwise angle between all vectors from distinct bases is $\arccos(1/\sqrt{d})$ . The largest number $μ(d)$ of MUBs that can exist in $\mathbb{C}^d$ is at most $d+1$ , but constructions attaining this bound are known only when $d$ is a prime power. A set of $b$ MUBs in $\mathbb{C}^d$ that cannot be enlarged, even by the first vector of a potential $(b+1)$ -th MUB, is called strongly unextendible. Until now, only one infinite family of dimensions $d$ containing $b(d)$ strongly unextendible MUBs in $\mathbb{C}^d$ satisfying $b(d) < μ(d)$ was known, this family, due to Szántó, is asymptotically "large" in the sense that $b(d)/μ(d) \to 1$ as $d \to \infty$ . However, the existence of $2^{m-1}+1$ strongly unextendible MUBs in $\mathbb{C}^{2^m}$ for each integer $m > 1$ has been conjectured by Mandayam et al. We prove their conjecture for all even values of $m$ , using only elementary linear algebra. The existence of this "small" new infinite family suggests, contrary to widespread belief, that $μ(d)$ for non-prime-powers $d$ might be significantly larger than the size of particular unextendible sets.

preprint2016arXiv

Constructions and nonexistence results for suitable sets of permutations

A set of $N$ permutations of $\{1,2,\dots,v\}$ is $(N,v,t)$ -suitable if each symbol precedes each subset of $t-1$ others in at least one permutation. The central problems are to determine the smallest $N$ for which such a set exists for given $v$ and $t$ , and to determine the largest $v$ for which such a set exists for given $N$ and $t$ . These extremal problems were the subject of classical studies by Dushnik in 1950 and Spencer in 1971. We give examples of suitable sets of permutations for new parameter triples $(N,v,t)$ . We relate certain suitable sets of permutations with parameter $t$ to others with parameter $t+1$ , thereby showing that one of the two infinite families recently presented by Colbourn can be constructed directly from the other. We prove an exact nonexistence result for suitable sets of permutations using elementary combinatorial arguments. We then establish an asymptotic nonexistence result using Ramsey's theorem.

preprint2015arXiv

A simple construction of complex equiangular lines

A set of vectors of equal norm in $\mathbb{C}^d$ represents equiangular lines if the magnitudes of the inner product of every pair of distinct vectors in the set are equal. The maximum size of such a set is $d^2$ , and it is conjectured that sets of this maximum size exist in $\mathbb{C}^d$ for every $d \geq 2$ . We describe a new construction for maximum-sized sets of equiangular lines, exposing a previously unrecognized connection with Hadamard matrices. The construction produces a maximum-sized set of equiangular lines in dimensions 2, 3 and 8.

preprint2015arXiv

Constructions of complex equiangular lines from mutually unbiased bases

A set of vectors of equal norm in $\mathbb{C}^d$ represents equiangular lines if the magnitudes of the Hermitian inner product of every pair of distinct vectors in the set are equal. The maximum size of such a set is $d^2$ , and it is conjectured that sets of this maximum size exist in $\mathbb{C}^d$ for every $d \geq 2$ . We take a combinatorial approach to this conjecture, using mutually unbiased bases (MUBs) in the following 3 constructions of equiangular lines: (1) adapting a set of $d$ MUBs in $\mathbb{C}^d$ to obtain $d^2$ equiangular lines in $\mathbb{C}^d$ , (2) using a set of $d$ MUBs in $\mathbb{C}^d$ to build $(2d)^2$ equiangular lines in $\mathbb{C}^{2d}$ , (3) combining two copies of a set of $d$ MUBs in $\mathbb{C}^d$ to build $(2d)^2$ equiangular lines in $\mathbb{C}^{2d}$ . For each construction, we give the dimensions $d$ for which we currently know that the construction produces a maximum-sized set of equiangular lines.

preprint2015arXiv

Large sets of complex and real equiangular lines

Large sets of equiangular lines are constructed from sets of mutually unbiased bases, over both the complex and the real numbers.

preprint2013arXiv

Advances in the merit factor problem for binary sequences

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.

preprint2013arXiv

Littlewood Polynomials with Small $L^4$ Norm

Littlewood asked how small the ratio $||f||_4/||f||_2$ (where $||.||_α$ denotes the $L^α$ norm on the unit circle) can be for polynomials $f$ having all coefficients in $\{1,-1\}$ , as the degree tends to infinity. Since 1988, the least known asymptotic value of this ratio has been $\sqrt[4]{7/6}$ , 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 $\sqrt[4]{22/19}$ .

preprint2012arXiv

The L_4 norm of Littlewood polynomials derived from the Jacobi symbol

Littlewood raised the question of how slowly the L_4 norm ||f||_4 of a Littlewood polynomial f (having all coefficients in {-1,+1}) of degree n-1 can grow with n. We consider such polynomials for odd square-free n, where ϕ(n) coefficients are determined by the Jacobi symbol, but the remaining coefficients can be freely chosen. When n is prime, these polynomials have the smallest known asymptotic value of the normalised L_4 norm ||f||_4/||f||_2 among all Littlewood polynomials, namely (7/6)^{1/4}. When n is not prime, our results show that the normalised L_4 norm varies considerably according to the free choices of the coefficients and can even grow without bound. However, by suitably choosing these coefficients, the limit of the normalised L_4 norm can be made as small as the best known value (7/6)^{1/4}.

preprint2011arXiv

Comment on revised version of "The Hadamard circulant conjecture"

The revised version of the claim by Hurley, Hurley and Hurley to have proved the circulant Hadamard matrix conjecture is mistaken.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jonathan Jedwab

Research overview

Is this your work?

13 publications

A group-based structure for perfect sequence covering arrays

An infinite class of unsaturated rooted trees corresponding to designable RNA secondary structures

Which graphs occur as $γ$ -graphs?

A new structure for difference matrices over abelian $p$ -groups

An infinite family of strongly unextendible mutually unbiased bases in $\mathbb{C}^{2^{2h}}$

Constructions and nonexistence results for suitable sets of permutations

A simple construction of complex equiangular lines

Constructions of complex equiangular lines from mutually unbiased bases

Large sets of complex and real equiangular lines

Advances in the merit factor problem for binary sequences

Littlewood Polynomials with Small $L^4$ Norm

The L_4 norm of Littlewood polynomials derived from the Jacobi symbol

Comment on revised version of "The Hadamard circulant conjecture"

See the researcher in context

Building this map preview

Jonathan Jedwab

Research overview

Is this your work?

13 publications

A group-based structure for perfect sequence covering arrays

An infinite class of unsaturated rooted trees corresponding to designable RNA secondary structures

Which graphs occur as γγγ-graphs?

A new structure for difference matrices over abelian ppp-groups

An infinite family of strongly unextendible mutually unbiased bases in C22h\mathbb{C}^{2^{2h}}C22h

Constructions and nonexistence results for suitable sets of permutations

A simple construction of complex equiangular lines

Constructions of complex equiangular lines from mutually unbiased bases

Large sets of complex and real equiangular lines

Advances in the merit factor problem for binary sequences

Littlewood Polynomials with Small L4L^4L4 Norm

The L_4 norm of Littlewood polynomials derived from the Jacobi symbol

Comment on revised version of "The Hadamard circulant conjecture"

See the researcher in context

Building this map preview

Which graphs occur as $γ$ -graphs?

A new structure for difference matrices over abelian $p$ -groups

An infinite family of strongly unextendible mutually unbiased bases in $\mathbb{C}^{2^{2h}}$

Littlewood Polynomials with Small $L^4$ Norm