🔢 mathematics

Log-Concavity and Infinite Log-Concavity of Linear Recurrent Sequences with Linear Coefficients via Companion Matrix Methods

This paper employs companion matrix methods to establish sufficient conditions for log-concavity in P-recursive sequences with linear coefficients and derives tight necessary and sufficient criteria for infinite log-concavity in specific second-order cases.

Original authors: Piero Giacomelli

Published 2026-04-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Piero Giacomelli

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

Imagine you have a line of dominoes, but instead of just falling over, each domino has a special number written on it. Let's call this line of numbers a sequence.

Mathematicians love these sequences because they often hide beautiful patterns. One specific pattern they look for is called Log-Concavity.

The "Goldilocks" Rule: What is Log-Concavity?

Think of three dominoes standing in a row: a small one, a big one, and a medium one.

Log-concave means the middle one is "big enough" compared to its neighbors.
Mathematically, it means: (Middle Number)² ≥ (Left Number) × (Right Number).

If this rule holds for every trio in your line, the sequence is "log-concave." It's a sign of stability and smoothness.

But here is the twist: What if we apply this rule again to the new numbers we just created? And then again?

Infinite Log-Concavity means the sequence is so perfectly smooth that no matter how many times you apply this "smoothness test," it keeps passing. It never breaks.

The Problem: The Shape-Shifting Machine

In this paper, the author, Piero Giacomelli, studies sequences that are generated by a specific type of machine.

The Machine: A "recurrence relation." This is a recipe where the next number is made by mixing the previous numbers together.
The Catch: The recipe changes as you go. The "mixing coefficients" aren't constant; they grow or shrink depending on how far you are in the line (they are linear functions of $n$ ).

Imagine a baker who makes bread.

Constant Recipe: "Add 2 cups of flour to the previous batch." (Easy to predict).
Variable Recipe: "Add $n$ cups of flour to the previous batch." (The recipe gets harder to predict as the number of batches grows).

The author wants to know: Can we predict if this "shifting recipe" will produce a sequence that is infinitely smooth (infinitely log-concave)?

The Solution: The "Companion Matrix" (The Magic Blueprint)

To solve this, the author uses a tool called the Companion Matrix.

The Analogy: Imagine the sequence isn't just a line of numbers, but a moving robot. The "Companion Matrix" is the robot's blueprint.
Usually, a blueprint is a static picture. But because the recipe changes with $n$ , this blueprint is a shape-shifting blueprint. It changes slightly with every step the robot takes.

The author's big breakthrough is realizing that the "smoothness test" (Log-Concavity) can be translated into a question about this blueprint.

Instead of checking every single number in the sequence, you just need to check if the blueprint (a specific mathematical grid called a matrix) is "positive."
If the blueprint is "positive" (mathematically speaking, positive semi-definite), then the sequence is guaranteed to be smooth. It's like checking if the foundation of a building is solid; if the foundation is good, the whole building stands.

The Special Cases: When the Rules Get Simple

The author found that for most complex, shape-shifting recipes, predicting infinite smoothness is incredibly hard (maybe even impossible to solve perfectly). However, he found three special "magic zones" where the answer is crystal clear:

The "Steady" Recipe (Constant Coefficients):
- If the recipe doesn't change (the coefficients are constant), the smoothness test becomes a geometric pattern.
- The Result: If the sequence passes the test once, it passes it forever. It's like a perfect circle; if it's round once, it's round forever.
The "Frozen" Recipe (Fixed Points):
- Some sequences are so special that applying the smoothness test to them just gives you the same sequence back.
- The Result: For these, the sequence is infinitely smooth if and only if all the numbers are positive. It's like a mirror that only reflects light if the room is bright.
The "Dominant" Recipe (Asymptotic Behavior):
- Some sequences eventually settle down and start behaving like a simple, steady recipe, even if they were chaotic at the start.
- The Result: If the sequence eventually settles into a smooth rhythm, then checking the start is enough to know it will stay smooth forever.

Why Does This Matter?

This paper is like finding a shortcut through a dense forest.

Before, to check if a complex sequence was "infinitely smooth," you might have had to check every single number, forever.
Now, the author gives us a map (the matrix method). For many sequences, we can just look at the map's foundation (the matrix) and know the answer immediately.

The Bottom Line

The paper says: "We can't solve this for every possible changing recipe in the universe (that's a famous unsolved math problem). But, we have built a powerful new tool that solves it for a huge class of recipes, and we know exactly when the tool works and when it stops working."

It turns a messy, infinite problem into a clean, finite check using the geometry of matrices. It's a beautiful example of how abstract math can find order in chaos.

1. Problem Statement

The paper addresses the characterization of log-concavity and $\infty$ -log-concavity for a specific class of sequences known as P-recursive (or holonomic) sequences.

Log-concavity: A sequence $(a_n)$ is log-concave if $a_n^2 \ge a_{n+1}a_{n-1}$ for all $n \ge 1$ .
$\infty$ -log-concavity: A sequence is $\infty$ -log-concave if the iterated application of the log-concave operator $L$ (where $L(a_n)_k = a_k^2 - a_{k+1}a_{k-1}$ ) yields non-negative sequences for all iterations $i \ge 1$ .

The specific focus is on sequences satisfying a linear recurrence of order $d$ where the coefficients are linear functions of $n$ :
$a_{n+1} = \sum_{k=0}^{d-1} (p_k n + q_k) a_{n-k}$
While sufficient conditions for log-concavity exist (e.g., via asymptotic behavior or real-rootedness), a tight (necessary and sufficient) criterion for general P-recursive sequences has remained elusive. Furthermore, the structural relationship between the log-concave operator $L$ and the companion matrix representation of these recurrences had not been previously investigated.

2. Methodology

The author employs a companion matrix approach to transform the scalar recurrence into a vector-matrix system, allowing for the analysis of log-concavity via quadratic forms.

State Vector Representation: The recurrence is rewritten as a first-order system $v_{n+1} = M_n v_n$ , where $v_n = (a_n, a_{n-1}, \dots, a_{n-d+1})^\top$ .
Affine Companion Matrix: The transition matrix $M_n$ is an affine function of $n$ :
$M_n = nA + B$
where $A$ and $B$ are constant matrices derived from the coefficients $p_k$ and $q_k$ .
Quadratic Form Derivation: The core methodological innovation is expressing the log-concave term $b_n = a_n^2 - a_{n+1}a_{n-1}$ as a quadratic form in the state vector $v_n$ :
$b_n = v_n^\top Q_n v_n$
The matrix $Q_n$ is explicitly constructed as $Q_n = Q(0) + nQ(1)$ , where $Q(0)$ and $Q(1)$ are symmetric matrices dependent on $A$ and $B$ .
Iterative Analysis: The paper analyzes the behavior of iterates $L^i(a_n)$ by examining the properties of $Q_n$ and the asymptotic behavior of the sequence, particularly in cases where the recurrence simplifies (e.g., constant coefficients).

3. Key Contributions and Results

A. General Matrix Criterion for Log-Concavity

The paper establishes that log-concavity is equivalent to the non-negativity of a quadratic form defined by $Q_n$ .

Theorem 3.3: $b_n \ge 0$ for all $n$ if and only if $v_n^\top Q_n v_n \ge 0$ .
Sufficient Condition: If the matrix $Q_n$ is positive semi-definite (PSD) for all $n \ge 1$ , the sequence is log-concave.
Asymptotic Guarantee: If $Q(1)$ is positive definite, then $Q_n$ becomes PSD for all sufficiently large $n$ , providing a condition for eventual log-concavity.
Initial Data Dependence: The condition can be reduced to a constraint on the initial vector $v_0$ via the product of companion matrices $\Pi_n$ .

B. Tight Criteria for Special Cases

The paper derives necessary and sufficient conditions for $\infty$ -log-concavity in three specific structural scenarios:

Second-Order Constant Coefficients ( $a_{n+1} = \alpha a_n + \beta a_{n-1}$ ):
- Key Insight: For this case, the sequence of log-concave terms $(b_n)$ is itself a geometric sequence. Consequently, the second iterate $L^2(a_n)$ is identically zero for $n \ge 2$ .
- Result: The sequence is $\infty$ -log-concave if and only if it is log-concave.
- Condition: Log-concavity holds iff $\beta < 0$ and the product of the coefficients in the general solution ( $A \cdot B$ ) is non-positive (or zero). This defines a closed convex cone of initial data $(a_0, a_1)$ .
Sequences Fixed by $L$ ( $L(a_n) = a_n$ ):
- Result: If a sequence is a fixed point of the operator, it is $\infty$ -log-concave if and only if the sequence itself is non-negative ( $a_n \ge 0$ ).
- Examples: $a_n = \cosh(n\theta)$ is $\infty$ -log-concave, while $a_n = \cos(n\theta)$ is not (due to sign changes).
P-Recursive Sequences with Dominant Real Roots:
- Assumptions: The sequence has a dominant real characteristic root $\Lambda_1$ , positive terms, and a monotone Turán ratio converging to a limit $< 1$ .
- Result: Under these asymptotic conditions, $\infty$ -log-concavity is equivalent to simple log-concavity.

C. Limitations and Decidability

General Case: The paper argues that a general finite tight criterion for arbitrary P-recursive sequences likely does not exist. This is because $L(a_n)$ for a general P-recursive sequence results in a sequence of higher complexity, and the positivity problem for general P-recursive sequences is known to be undecidable (or at least not known to be decidable).

4. Illustrative Examples

The paper validates the theory with several examples:

Fibonacci-type: Shows that standard Fibonacci numbers ( $a_{n+1} = a_n + a_{n-1}$ ) are generally not log-concave because the product of roots is negative, causing sign alternation in $b_n$ .
Variable Coefficients: Demonstrates a case where $Q_n$ is PSD for all $n$ , guaranteeing log-concavity even if the sequence terms $a_n$ change signs (e.g., $a_2=2, a_3=-5$ but $b_2 > 0$ ).
Counter-examples: Shows sequences where $Q(1)$ is not PSD, leading to a failure of log-concavity for large $n$ .

5. Significance and Future Directions

Theoretical Advancement: This work bridges the gap between linear recurrence theory and log-concavity by providing a unified matrix framework. It moves beyond asymptotic sufficient conditions to provide exact algebraic criteria for specific, important classes of sequences.
Computational Utility: The quadratic form criterion ( $v_0^\top R_n v_0 \ge 0$ ) offers a concrete method to test log-concavity for specific initial data without computing the entire sequence.
Open Problems: The paper outlines several open questions, including:
- Characterizing the geometry of the cone of initial data for higher-order ( $d \ge 3$ ) sequences.
- Extending the quadratic form analysis to recurrences with polynomial coefficients of degree $\ge 2$ .
- Resolving the decidability of $\infty$ -log-concavity for general P-recursive sequences.
- Applying these methods to the rows of Pascal's triangle in the context of the Boros–Moll conjecture.

In summary, Giacomelli's paper provides a rigorous algebraic framework using companion matrices to analyze log-concavity, successfully solving the problem for constant-coefficient and specific asymptotic cases while highlighting the inherent complexity of the general case.