🔢 mathematics

Greedy Regular Convolutions

This paper introduces a class of bounded, regular, and homogeneous "greedy" convolutions on arithmetical functions, highlighting the unitary and ternary convolutions as unique cases where all primitive numbers share the same finite rank, while also detailing a length-3 variant generated by a novel "selective sifting" procedure.

Original authors: Jan Snellman

Published 2026-08-18

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Jan Snellman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Mathematics often feels like the study of static objects: shapes, numbers, and the fixed rules that govern them. Yet, there is a vibrant branch of number theory dedicated to how numbers interact when combined. Imagine a vast library where every book represents a whole number. Mathematicians have long sought a universal way to pair these books together, creating new numbers through a process called convolution. This is not simple addition or multiplication, but a sophisticated method of mixing information based on the hidden structure of each number's factors. For decades, researchers have classified these pairings, finding that some are perfectly uniform, like a grid of identical tiles, while others are more complex. The central question has been whether one can create a pairing system that is both orderly and strictly limited in size, yet flexible enough to handle every possible number without leaving gaps.

In a recent study, Jan Snellman from Linköping University tackles this puzzle by introducing a new way to build these number pairings, which he calls "greedy convolutions." The goal was to construct a system where the rules for combining numbers are consistent across all prime numbers, but the groups of numbers involved are kept small and finite. Previous work had shown that if you demand every group be exactly the same size, you are limited to only two possibilities: a system where groups contain just one number, and another where they contain exactly two. Snellman asked what would happen if he relaxed that rule slightly. Instead of forcing every group to be the same size, he proposed a "greedy" approach: take the numbers in order, one by one, and place each new number into the first available group that has room for it, up to a maximum size limit.

The results of this simple, step-by-step procedure reveal a surprising landscape. When the limit is set to one, the method reproduces the known system of single-number groups. When the limit is two, it recreates the known system of two-number groups. However, as soon as the limit is raised to three, the system changes in a fundamental way. The groups are no longer all the same size; some contain three numbers, while others contain only one. The researcher mapped out exactly how these groups form, discovering that the numbers which start a new group—called primitive elements—follow a specific, intricate pattern. For the case of a limit of three, the researcher found that these starting numbers make up a specific portion of all whole numbers, occurring with a predictable frequency.

The study goes further by introducing a method called "selective sifting" to describe these starting numbers. This process is like a filter that removes certain numbers based on whether they can be built from smaller, already-selected numbers. For the case of a limit of three, this filter perfectly identifies the starting numbers. However, when the researcher tried to apply this same logic to a limit of four, the pattern broke down. The starting numbers for the limit of four do not fit neatly into the existing filter. Instead, they appear to follow a more complex, almost chaotic rule that the researcher can only describe through a rough guess supported by computer simulations. The study confirms that while the rule for building the groups is straightforward, the resulting structure becomes increasingly difficult to predict as the size limit grows.

The paper also settles a long-standing question about whether it is possible to have a system where every group is the same size, provided that size is larger than two. The researcher proved that such a system cannot exist. If one tries to force every group to be the same size, the greedy process inevitably leaves some groups incomplete, creating a gap in the system. This confirms that the two known systems are the only ones of their kind where every group is identical. The work leaves open the question of exactly how the starting numbers are distributed for larger limits, suggesting that the deeper one looks into these greedy systems, the more complex and less uniform the underlying order becomes.

Technical Summary: Greedy Regular Convolutions

Problem Statement
The paper addresses the classification and construction of regular convolutions on the set of arithmetical functions ( $\Gamma$ ). Building on Narkiewicz's classification, which defines regular convolutions via families of decompositions of the natural numbers $\mathbb{N}$ into arithmetic progressions containing zero, the author investigates the specific class of homogeneous and bounded regular convolutions.

A regular convolution is homogeneous if the decomposition structure is identical for all prime numbers $p$ , and bounded if the lengths of the arithmetic progression blocks are uniformly bounded by some integer $M$ . While the Dirichlet convolution (unbounded) and the unitary convolution (bounded, block-length 1) are well-known, and the ternary convolution (bounded, block-length 2) was identified by Gavell, a gap exists in understanding regular convolutions where the block-length $d > 2$ . Specifically, Gavell proved that for $d > 2$ , no regular homogeneous convolution exists where all blocks have the exact same length $d$ . The paper seeks to define a canonical convolution for any $d$ that approximates this uniformity by filling blocks as much as possible, leading to the concept of "greedy" convolutions.

Methodology
The author introduces a constructive procedure to generate these convolutions, termed greedy convolutions of length $d$ . The methodology relies on two primary representations:

Tree Construction: For a given $d$ , a sequence of rooted trees $T_d(n)$ is defined on vertices $\{0, 1, \dots, n\}$ . Integers are added sequentially. An integer $n+1$ is attached as a leaf to an existing branch $0 \to k \to 2k \to \dots \to mk$ if $n+1 = (m+1)k$ and $m+1 \le d$ . If multiple such branches exist, the one with the smallest $k$ is chosen (the "greedy" rule). If no such branch exists, a new branch $0 \to (n+1)$ is started. The limit of these trees defines the decomposition $\Pi(d)$ of $\mathbb{N}$ .
Matrix Representation: The decomposition is equivalently generated by a $d \times \mathbb{N}$ matrix $A(d, N)$ where entry $(i, j) = ij$. Columns are processed; if a value $ar,c$ appears in an earlier column, the current column is "pruned" (set to zero below row $r$ ). The non-zero columns represent the parts of the partition $S(d)$ of $\mathbb{P}$ (positive integers).

The paper utilizes the concept of primitive elements (the smallest positive element in each block of the decomposition) to characterize the algebraic structure. To analyze the set of primitive elements for $d=2$ and $d=3$ , the author introduces a recursive sieve-like procedure named selective sifting, denoted $s(S)$ . This procedure iteratively includes an integer $n$ in the set unless it can be formed as $ab$ where $a \in S$ and $b$ is already in the sifted set.

Key Contributions and Results

Definition of Greedy Convolutions: The paper formally defines the greedy convolution $G(d)$ for any positive integer $d$ . It establishes that $G(1)$ corresponds to the unitary convolution and $G(2)$ corresponds to the ternary convolution.
Uniqueness of Uniform Block Lengths: The paper provides a proof (attributed to Gavell) that for $d > 2$ , no regular homogeneous convolution exists where all blocks have the exact same length $d$ . The greedy construction is presented as the natural alternative where block lengths are $\le d$ , but not necessarily equal.
Detailed Analysis of $d=3$ :
- The block lengths for $G(3)$ are shown to be either 3 or 1.
- The set of primitive elements is partitioned into those of full rank (3) and rank 1.
- The set of primitives of full rank, $M$ , is identified as the set of integers $m$ such that $m = 4^i 9^j k$ with $\gcd(k, 6)=1$ (OEIS A339690).
- The set of rank-1 primitives is identified as $6M$ .
- The natural density of the full set of primitives for $d=3$ is calculated to be $7/12$ .
- The author demonstrates that the set of primitives for $d=3$ can be described via selective sifting with the set $S = \{2, 3, 6\}$ .
Selective Sifting Framework: The paper generalizes the sifting method, providing closed-form descriptions for $s(\{p\})$ , $s(\{p, q, pq\})$ , and other specific sets. It establishes that for $d=2$ and $d=3$ , the primitive sets are exactly $s(S)$ for specific $S$ .
Analysis of $d=4$ :
- The paper presents data for $G(4)$ , noting the existence of primitives of rank 1, 2, and 4, but the absence of rank 3 primitives.
- It is observed that the set of primitives for $d=4$ cannot be exactly represented by a finite selective sifting set $S$ .
- A conjecture is proposed that the set of rank-4 primitives is "close" to a selective sifting set generated by an infinite $S$ consisting of numbers of the form $2^a 3^b$ .
Statistical Properties: The paper calculates natural densities for various cases and plots the distribution of block lengths and distances between consecutive primitives, noting that the average distance between primitives is the reciprocal of their natural density.

Significance and Claims
The paper claims to provide a systematic construction for a new family of regular convolutions that fill the gap between the unitary/ternary cases and higher-order uniform block lengths. The primary significance lies in:

Structural Characterization: Proving that uniform block lengths are impossible for $d > 2$ and offering the greedy construction as the canonical solution.
Intricate Primitive Structure: Revealing that while the definition of greedy convolutions is straightforward, the structure of their primitive elements becomes surprisingly complex for $d \ge 3$ . The paper highlights that for $d=3$ , the structure is regular and describable by selective sifting, but for $d=4$ , the structure becomes "surprisingly intricate" and resists simple sifting descriptions.
Open Problems: The paper concludes by posing several open questions regarding the ranks of primitive elements, their natural densities for general $d$ , and the precise structure of the "sporadic" elements in higher-length greedy convolutions.

The author explicitly states that the results are derived from the definitions and computational experiments (using SageMath), and the paper does not claim applications outside the theoretical framework of arithmetical functions and regular convolutions. The work serves as a classification and exploration of these specific algebraic structures.

More like this