Combinatorics and statistics

Overlapping words in strings

I have  investigated the combinatorics and statistics of the overlapping of words in strings, leading to a book chapter [1], two integer sequences (A152139 and A152959) and the Suprangen software library. It has also resulted in a conjecture that, for all word lengths, the number of correlation classes for an alphabet of size greater than four is the same as that for an alphabet of size four. In an effort to disprove the conjecture, with Jörg Arndt, I have written and run an MPI-based C program that performs parallel combinatorial enumeration on the NCI Raijin cluster.

Presentations

• Testing the tests: using pseudorandom number generators to improve empirical tests, MCQMC, Montreal, 2008.

• Accurate computation of the variance of the number of missing words in a random string, 4ICC, Auckland, 2008.

• A conjecture on the alphabet size needed to produce all correlation classes of pairs of words, 34 ACCMCC, ANU, 2010.

Publications and preprints

1. Paul Leopardi, "Testing the tests: using random number generators to improve empirical tests", Monte Carlo and Quasi-Monte Carlo Methods 2008, Pierre L' Ecuyer, Art B. Owen (Eds.) Springer, 2009 pp. 501--512. ISBN: 978-3-642-04106-8, MR 2743916, (Citations). Preprint: Revised July 2009.

   • Examines implementations of the overlapping serial tests of Marsaglia and Zaman, and improves them, using accurate calculation of the mean and variance of the number of missing words in a random string.

Integer sequences

• A152139: Correlation classes of pairs of different words, November 2008.

• A152959: Number of correlation classes for pairs of different words in an alphabet of size 4, December 2008.

Open source software

• Suprangen: Sydney University pseudorandom number generators.

• Word-overlap: Various code used to compute word overlap correlations per Guibas and Odlyzko, Rahmann and Rivals, Rukhin.

Conjectures, questions

• Conjecture on required alphabet size to exhibit all correlation classes of pairs of words (Seqfan mailing list, 2009)

• Which automated theorem provers can address the combinatorics of periods in strings? (MathOverflow, 2014)

Alignment-free statistics of biological sequences

The combinatorics and related statistics of words in strings is the core of my research in bioinformatics. This has led to two joint papers [1,2], and the SAFT and PySAFT software packages. The work on PySAFT includes the implementation in Python of large, sparse matrix multiplication, using either MPI4Py or NumPy Memmap.

Presentations

• Determining the distribution of word matches between Markovian sequences, CTAC 2012.

• Alignment-free comparison of biological sequences, ANZIAM 2013.

Publications and preprints

1. Conrad Burden, Paul Leopardi and Sylvain Fôret, "The distribution of word matches between Markovian sequences with periodic boundary conditions", Journal of Computational Biology, 21(1), January 2014, pp. 41--63. DOI 10.1089/cmb.2012.0277 .  Preprint: Revised May 2013.

   • Further examines the D2 statistic, which counts the number of word matches between two given sequences, under the assumptions of periodic boundary conditions and Markovian dependence. Includes the calculation of the mean of D2 for all Markov orders and the variance for all Markov orders up to and including the word length. Also includes a comparison of synthetic data with DNA data from human chromosome 1.

2. Conrad Burden, Paul Leopardi and Sylvain Fôret, "Word match counts between Markovian sequences","Biomedical Engineering Systems and Technologies 6th International Joint Conference, BIOSTEC 2013", Springer series on Communications in Computer and Information Science, 2014, pp. 147-161. Preprint of conference paper: ("The distribution of short word match counts between Markovian sequences"), presented at International Conference on Bioinformatics Models, Methods and Algorithms (Bioinformatics 2013). November 2012. Preprint of revised and extended paper: June 2013.

   • Examines the D2 statistic, which counts the number of word matches between two given sequences, under the assumptions of periodic boundary conditions and Markovian dependence. Includes the calculation of the mean of D2 for all Markov orders and the variance for Markov order 1.

Open source software

• PySAFT: Prototype of (potentially faster) version of SAFT using SciPy sparse matrix multiplication

• SAFT: Sequence Alignment-Free Tool. (Forked from sylvainforet/saft).

Clifford algebras and constructions for Hadamard matrices

I am investigating constructions for Hadamard matrices, as per my paper [1]. This resulted in a conjecture that an edge-coloured graph related to the Cayley graph of a bent function has an isomorphism that swaps the colours. I proved that twin bent functions are involved, and presented this work at the ADTHM 2014 workshop in Lethbridge [2]. In later work I showed that the corresponding bent functions have isomorphic Cayley graphs only in the first 3 cases [3]. This led to deeper work on the Cayley graphs of bent functions [4], and also to the correct formulation of the original problem on Hadamard matrices in terms of representations of Gastineau-Hills' quasi-Clifford algebras [5]. In these investigations, computer searches become prohibitively large very quickly.

Presentations

• Amicability graphs and Clifford algebras, Hadamard Maximal Determinant Workshop, ANU, 2010.

• Constructions for Hadamard matrices, Clifford algebras, and their relation to amicability - anti-amicability graphs, 35 ACCMCC, Monash University, 2011.

• New constructions for Hadamard matrices, CARMA Seminar, University of Newcastle, 2012.

• Skew, bent and fractious: a confession, AustMS, University of Sydney, 2013.

• Representations of Clifford algebras: skew, bent and fractious, 37 ACCMCC, University of Western Australia, 2013.

• Twin bent functions and Clifford algebras, ADTHM, Lethbridge, 2014 (revised), University of Newcastle, 2014.

• Twin strongly regular graphs: some questions, relayed by Robert Craigen at Algebraic design theory with Hadamard matrices: applications, current trends and future directions (14w2199), 2014.

• Twin bent functions, strongly regular Cayley graphs, and Hurwitz-Radon theory, University of Newcastle, 2015.

• Classifying bent functions by their Cayley graphs, 39 ACCMCC, University of Queensland, 2015.

• Classifying bent functions by their Cayley graphs, using Sage, 40 ACCMCC, University of Newcastle, 2016; RMIT 2017.

• Classifying bent functions by their Cayley graphs, 2 MCGTC, Malta, 2017.

• Classifying bent functions, University of Melbourne, 2017.

• Yet another database of strongly regular graphs, 5ICC, Monash University, 2017.

• Yet another database of strongly regular graphs: Classifying bent functions by their Cayley graphs, TFAA, Taipa, 2018.

• Gastineau-Hills' quasi-Clifford algebras and plug-in constructions for Hadamard matrices, AGACSE, Campinas, Brazil 2018; Symposium on Clifford Algebras, Mathematical Physics and Related Topics, Federal University of ABC, Brazil, 2018; 41 ACCMCC, Rotorua, 2018.

• Big data in combinatorics: is it FAIR?, 42 ACCMCC, UNSW Sydney, 2019.

• Relations between equivalence classes of bent functions, AustMS, University of Queensland, 2023.

Publications and preprints

1. Paul Leopardi, "Constructions for Hadamard matrices, Clifford algebras, and their relation to amicability / anti-amicability graphs", Australasian Journal of Combinatorics, Volume 58(2) (2014), pp. 214–248.  Preprint: Revised January 2014.  Supplementary material can be found in the Hadamard-fractious Github repository.

   • Describes how the pattern of commuting and anticommuting pairs of basis elements of a real Clifford algebra, and their representation theory, can be used in the construction of Hadamard matrices.

2. Paul Leopardi, "Twin bent functions and Clifford algebras", in C. Colbourn (ed.) Algebraic Design Theory and Hadamard Matrices (ADTHM 2014), Springer, 2015, pp. 189-199. Preprint:  arXiv:1501.05477 [math.CO].

   • Examines a pair of bent functions on and their relationship to a necessary condition for the existence of an automorphism of an edge-coloured graph, whose colours are defined by the properties of a canonical basis for the real representation of a real Clifford algebra.

3. Paul Leopardi, "Twin bent functions, strongly regular Cayley graphs, and Hurwitz-Radon theory", Journal of Algebra Combinatorics Discrete Structures and Applications, 4 (3) , 2017, pp. 271-280. Preprint: arXiv:1504.02827 [math.CO].

   • Uses a theorem of Radon to prove that the corresponding graphs in the two sequences of strongly regular graphs considered in [1] and [2] are not isomorphic, except in the first 3 cases.

4. Paul Leopardi, "Classifying bent functions by their Cayley graphs", rejected  by INTEGERS: The Electronic Journal of Combinatorial Number Theory, November 2018. Preprint: arXiv:1705.04507 [math.CO]. Revised, December, 2018.

   • Explores the connections between bent functions and their Cayley graphs, as well as projective two-weight linear codes, and symmetric designs with the symmetric difference property, through various equivalence classes. Includes exhaustive classifications of bent functions up to 8 dimensions and degree 3, with selected examples of degree 4.

5. Paul Leopardi, "Gastineau-Hills' quasi-Clifford algebras and plug-in constructions for Hadamard matrices". Advances in Applied Clifford Algebras (2019) 29: 48. Preprint: arXiv:1804.09454 [math.CO].

   • Applies the representation theory of quasi-Clifford algebras, as described by Gastineau-Hills, to the plug in constructions for Hadamard matrices described in [1].

Open source software

• Hadamard-fractious: Software, data and plots supporting the paper, "Constructions for Hadamard matrices, Clifford algebras, and their relation to amicability / anti-amicability graphs."

• Boolean-Cayley-graphs: Investigations of Boolean functions, their Cayley graphs, and associated structures.

  • CoCalc: public folder of worksheets, source code and data files.

  • GitHub: Git repository of source code, data and papers.

  • SourceForge: Documentation of Python modules in HTML format.