Source author record

Victor S. Miller

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics Information Theory math.GR math.IT math.PR

Catalog footprint

Research overview

3works

6topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Counting Matrices that are Squares

On the math-fun mailing list (7 May 2013), Neil Sloane asked to calculate the number of $n \times n$ matrices with entries in $\{0,1\}$ which are squares of other such matrices. In this paper we analyze the case that the arithmetic is in $\mathbb{F}_{2}$ . We follow the dictum of Wilf ("What is an answer?") to derive a "effective" algorithm to count such matrices in much less time than it takes to enumerate them. The algorithm which we use involves the analysis of conjugacy classes of matrices. The restricted integer partitions which arise are counted by the coefficients of one of Ramanujan's mock Theta functions, which we found thanks to Sloane's OEIS (Online Encyclopedia of Integer Sequences). Let $a_n$ be the number elements of ${\rm Mat}_n(\mathbb{F}_{2})$ which are squares, and $b_n$ be the number of elements of ${\rm GL}(n,\mathbb{F}_{2})$ which are squares. The numerical results strongly suggest that there are constants $α,β> 0$ such that $a_n \sim α2^{n^2}$ , $b_n \sim β2^{n^2}$ .

preprint2014arXiv

Extensions of Billingsley's Theorem via Multi-Intensities

Let $p_1 \ge p_2 \ge \dots$ be the prime factors of a random integer chosen uniformly from $1$ to $n$ , and let $\frac{\log p_1}{\log n}, \frac{\log p_2}{\log n}, \dots$ be the sequence of scaled log factors. Billingsley's Theorem (1972), in its modern formulation, asserts that the limiting process, as $n \to \infty$ , is the Poisson-Dirichlet process with parameter $θ=1$ . In this paper we give a new proof, inspired by the 1993 proof by Donnelly and Grimmett, and extend the result to factorizations of elements of normed arithmetic semigroups satisfying certain growth conditions, for which the limiting Poisson-Dirichlet process need not have $θ=1$ . We also establish Poisson-Dirichlet limits, with $θ\ne 1$ , for ordinary integers conditional on the number of prime factors deviating from the usual value $\log \log n$ . At the core of our argument is a purely probabilistic lemma giving a new criterion for convergence in distribution to a Poisson-Dirichlet process, from which the number-theoretic applications follow as straightforward corollaries. The lemma uses ingredients similar to those employed by Donnelly and Grimmett, but reorganized so as to allow subsequent number theory input to be processed as rapidly as possible. A by-product of this work is a new characterization of Poisson-Dirichlet processes in terms of multi-intensities.

preprint2011arXiv

Binary Non-tiles

A subset V of GF(2)^n is a tile if GF(2)^n can be covered by disjoint translates of V. In other words, V is a tile if and only if there is a subset A of GF(2)^n such that V+A = GF(2)^n uniquely (i.e., v + a = v' + a' implies that v=v' and a=a' where v,v' in V and a,a' in A). In some problems in coding theory and hashing we are given a putative tile V, and wish to know whether or not it is a tile. In this paper we give two computational criteria for certifying that V is not a tile. The first involves impossibility of a bin-packing problem, and the second involves infeasibility of a linear program. We apply both criteria to a list of putative tiles given by Gordon, Miller, and Ostapenko in that none of them are, in fact, tiles.

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.