# Generalizations of Fermat’s Little Theorem and combinatorial zeta functions

Everyone who studies elementary number theory learns two different versions of Fermat’s Little Theorem:

Fermat’s Little Theorem, Version 1: If $p$ is prime and $a$ is an integer not divisible by $p$, then $a^{p-1} \equiv 1 \pmod{p}$.

Fermat’s Little Theorem, Version 2: If $p$ is prime and $a$ is any integer, then $a^{p} \equiv a \pmod{p}$.

as well as the following extension of Version 1 of Fermat’s Little Theorem to arbitrary positive integers $n$:

Euler’s Theorem: If $n$ is a positive integer and $(a,n)=1$, then $a^{\phi(n)} \equiv 1 \pmod{n}$, where $\phi$ is Euler’s totient function.

My first goal in this post is to explain a generalization of Version 2 of Fermat’s Little Theorem to arbitrary $n$. I’ll then explain an extension of this result to $m \times m$ integer matrices, along with a slick proof of all of these results (and more) via “combinatorial zeta functions”.

# Interlacing via rational functions and spectral decomposition

First of all, I’d like to express my sympathies to everyone who is enduring hardships due to COVID-19. Stay well and be strong.

In this previous post, I discussed two important classical results giving examples of polynomials whose roots interlace:

Theorem 1: The roots of a real-rooted polynomial and its derivative interlace.

Theorem 2: (Cauchy’s interlacing theorem) The eigenvalues of a real symmetric matrix interlace with those of any principal minor.

In this post, I’d like to explain a general method, based on partial fraction expansions of rational functions, which gives a unified approach to proving Theorems 1 and 2 and deserves to be better known.

# Lorentzian polynomials I: Theory

I’m organizing a reading seminar this semester on Lorentzian polynomials, mainly following this paper by Brändén and Huh but also covering some of the work of Anari et. al. In this post, I’d like to give a quick introduction to this active and beautiful subject. I’ll concentrate on the basic theory for now, and in a follow-up post I’ll discuss some of the striking applications of this theory.

One major goal of the theory of Lorentzian polynomials is to provide new techniques for proving that various naturally-occurring sequences of non-negative real numbers $a_k$ are log-concave, meaning that $a_k^2 \geq a_{k-1} a_{k+1}$ for all $k$. More generally, the authors consider homogeneous multivariate polynomials $p(x_1,\ldots,x_n)$ with non-negative coefficients and study certain natural extensions of log-concavity to this setting. (For some background on log-concave sequences, see this survey paper which I wrote for the Bulletin of the AMS.) So let me begin by introducing two “classical” methods for proving (an even sharper version of) log-concavity of the coefficients of certain polynomials.

In Part I of this post, we defined hyperrings and hyperfields, gave some key examples, and introduced matroids over (doubly distributive) hyperfields in terms of Grassman-Plücker functions.  If $E=\{ 1,\ldots,m \}$ is a finite set and $K$ is a field, we saw that a $K$-matroid on $E$ is the same thing as a linear subspace of $K^m$, and if ${\mathbb K}$ is the Krasner hyperfield then a ${\mathbb K}$-matroid on $E$ is the same thing as a matroid in the usual sense.  Matroids over the hyperfield ${\mathbb S}$ of signs are the same thing as oriented matroids, and matroids over the tropical hyperfield ${\mathbb T}$ are the same thing as valuated matroids.  In this post we will give some “cryptomorphic” axiomatizations of matroids over hyperfields, discuss duality theory, and then discuss the category of hyperrings in a bit more detail. Continue reading