Source author record

Noah Kravitz

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

ResearcherUnclaimed source record

math.CO math.NT math.CA

Catalog footprint

Research overview

7works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

The structure of Lonely Runner spectra

For each subtorus $T$ of $(\mathbb{R}/\mathbb{Z})^n$ , let $D(T)$ denote the (infimal) $L^\infty$ -distance from $T$ to the point $(1/2,\ldots, 1/2)$ . The $n$ -th Lonely Runner spectrum $\mathcal{S}(n)$ is defined to be the set of all values achieved by $D(T)$ as $T$ ranges over the $1$ -dimensional subtori of $(\mathbb{R}/\mathbb{Z})^n$ that are not contained in the coordinate hyperplanes. The Lonely Runner Conjecture predicts that $\mathcal{S}(n) \subseteq [0,1/2-1/(n+1)]$ . Rather than attack this conjecture, we study the structure of the sets $\mathcal{S}(n)$ . The main purpose of this note is to show that the set of accumulation points of $\mathcal{S}(n)$ is precisely $\mathcal{S}(n-1)$ .

preprint2022arXiv

Loops and Regions in Hitomezashi Patterns

Hitomezashi patterns, which originate from traditional Japanese embroidery, are intricate arrangements of unit-length line segments called stitches. The stitches connect to form hitomezashi strands and hitomezashi loops, which divide the plane into regions. We investigate the deeper mathematical properties of these patterns, which also feature prominently in the study of corner percolation. It was previously known that every loop in a hitomezashi pattern has odd width and odd height. We additionally prove that such a loop has length congruent to $4$ modulo $8$ and area congruent to $1$ modulo $4$ . Although these results are simple to state, their proofs require us to understand the delicate topological and combinatorial properties of slicing operations that can be applied to hitomezashi patterns. We also show that the expected number of regions in a random $m\times n$ hitomezashi pattern (chosen according to a natural random model) is asymptotically $\left(\frac{π^2-9}{12}+o(1)\right)mn$ .

preprint2020arXiv

Generalized difference sets and autocorrelation integrals

In 2010, Cilleruelo, Ruzsa, and Vinuesa established a surprising connection between the maximum possible size of a generalized Sidon set in the first $N$ natural numbers and the optimal constant in an ``analogous'' problem concerning nonnegative-valued functions on $[0,1]$ with autoconvolution integral uniformly bounded above. Answering a recent question of Barnard and Steinerberger, we prove the corresponding dual result about the minimum size of a so-called generalized difference set that covers the first $N$ natural numbers and the optimal constant in an analogous problem concerning nonnegative-valued functions on $\mathbb{R}$ with autocorrelation integral bounded below on $[0,1]$ . These results show that the correspondence of Cilleruelo, Ruzsa, and Vinuesa is representative of a more general phenomenon relating discrete problems in additive combinatorics to questions in the continuous world.

preprint2020arXiv

Inverse problems for minimal complements and maximal supplements

Given a subset $W$ of an abelian group $G$ , a subset $C$ is called an additive complement for $W$ if $W+C=G$ ; if, moreover, no proper subset of $C$ has this property, then we say that $C$ is a minimal complement for $W$ . It is natural to ask which subsets $C$ can arise as minimal complements for some $W$ . We show that in a finite abelian group $G$ , every non-empty subset $C$ of size $|C| \leq 2^{2/3}|G|^{1/3}/((3e \log |G|)^{2/3}$ is a minimal complement for some $W$ . As a corollary, we deduce that every finite non-empty subset of an infinite abelian group is a minimal complement. We also derive several analogous results for ``dual'' problems about maximal supplements.

preprint2020arXiv

Promotion Sorting

Schützenberger's promotion operator is an extensively-studied bijection that permutes the linear extensions of a finite poset. We introduce a natural extension $\partial$ of this operator that acts on all labelings of a poset. We prove several properties of $\partial$ ; in particular, we show that for every labeling $L$ of an $n$ -element poset $P$ , the labeling $\partial^{n-1}(L)$ is a linear extension of $P$ . Thus, we can view the dynamical system defined by $\partial$ as a sorting procedure that sorts labelings into linear extensions. For all $0\leq k\leq n-1$ , we characterize the $n$ -element posets $P$ that admit labelings that require at least $n-k-1$ iterations of $\partial$ in order to become linear extensions. The case in which $k=0$ concerns labelings that require the maximum possible number of iterations in order to be sorted; we call these labelings tangled. We explicitly enumerate tangled labelings for a large class of posets that we call inflated rooted forest posets. For an arbitrary finite poset, we show how to enumerate the sortable labelings, which are the labelings $L$ such that $\partial(L)$ is a linear extension.

preprint2020arXiv

Supertrees

A $k$ -universal permutation, or $k$ -superpermutation, is a permutation that contains all permutations of length $k$ as patterns. The problem of finding the minimum length of a $k$ -superpermutation has recently received significant attention in the field of permutation patterns. One can ask analogous questions for other classes of objects. In this paper, we study $k$ -supertrees. For each $d\geq 2$ , we focus on two types of rooted plane trees called $d$ -ary plane trees and $[d]$ -trees. Motivated by recent developments in the literature, we consider "contiguous" and "noncontiguous" notions of pattern containment for each type of tree. We obtain both upper and lower bounds on the minimum possible size of a $k$ -supertree in three cases; in the fourth, we determine the minimum size exactly. One of our lower bounds makes use of a recent result of Albert, Engen, Pantone, and Vatter on $k$ -universal layered permutations.

preprint2020arXiv

The smoothest average: Dirichlet, Fejér and Chebyshev

We are interested in the ``smoothest'' averaging that can be achieved by convolving functions $f \in \ell^2(\mathbb{Z})$ with an averaging function $u$ . More precisely, suppose $u:\{-n, \ldots, n\} \to \mathbb{R}$ is a symmetric function normalized to $\sum_{k=-n}^{n}u(k) = 1$ . We show that every convolution operator is not-too-smooth, in the sense that $\sup_{f \in \ell^2(\mathbb{Z})} \frac{\| \nabla (f*u)\|_{\ell^2(\mathbb{Z})}}{\|f\|_{\ell^2}}\geq \frac{2}{2n+1},$ and we show that equality holds if and only if $u$ is constant on the interval $\{-n, \ldots, n\}$ . In the setting where smoothness is measured by the $\ell^2$ -norm of the discrete second derivative and we further restrict our attention to functions $u$ with nonnegative Fourier transform, we establish the inequality $\sup_{f \in \ell^2(\mathbb{Z})} \frac{\| Δ(f*u)\|_{\ell^2(\mathbb{Z})}}{\|f\|_{\ell^2(\mathbb{Z})}} \geq \frac{4}{(n+1)^2},$ with equality if and only if $u$ is the triangle function $u(k)=(n+1-|k|)/(n+1)^2$ . We also discuss a continuous analogue and several open problems.

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.

Noah Kravitz

Research overview

Is this your work?

7 publications

The structure of Lonely Runner spectra

Loops and Regions in Hitomezashi Patterns

Generalized difference sets and autocorrelation integrals

Inverse problems for minimal complements and maximal supplements

Promotion Sorting

Supertrees

The smoothest average: Dirichlet, Fejér and Chebyshev

See the researcher in context

Building this map preview