This question arises from an application to graphical models in probability theory, but I have abstracted that part out so only algebra remains. Let $\mathbb{R}$ denote standard field of real numbers and $\mathcal{R} = (\mathbb{R}\cup\{\infty\},\min,+)$ the tropical semiring. Let $\mathbb{Z}_n$ denote the cyclic group of order $n$.

Elements of the group ring $\mathbb{R}\mathbb{Z}_n$ are tuples $(x_0,\ldots,x_{n-1})$ and multiplication of these corresponds to discrete cyclic convolution. The Fast Fourier Transform gives an isomorphism $\mathbb{R}\mathbb{Z}_n\to\mathbb{R}^n$ (with elementwise sum and product). The FFT and its inverse can be computed in $O(n\log n)$ arithmetic operations, so elements of $\mathbb{R}\mathbb{Z}_n$ can be multiplied in $O(n\log n)$ arithmetic operations.

Define the group semiring $\mathcal{R}\mathbb{Z}_n$ in an analogous way. The product of $x = (x_0,\ldots, x_{n-1})$ and $y = (y_0,\ldots,y_{n-1})$ in this semiring is given by $(x\cdot y)_k = \min _{j \in \mathbb{Z}_n} (x_j + y_{k-j})$. This operation could perhaps be called "discrete cyclic infimal convolution" by analogy with the notion of infimal convolution in convex analysis. I'm not sure whether there is a more standard name -- this one does not pop up in quick google searches.

The naive way of computing a discrete infimal convolution uses $O(n^2)$ operations, just as the naive method for computing a standard cyclic convolution. My question is: is there a way to compute this "discrete cyclic infimal convolution" in $O(n\log n)$ arithmetic operations?

In convex analysis, there is an analog of the Fourier transform which turns infimal convolution into pointwise addition: the convex conjugate (or Fenchel or Legendre transformation). However, this operation only behaves nicely for convex functions, so it is not clear to me how one would translate it to an equivalent tool for $\mathcal{R}\mathbb{Z}_n$, but perhaps there is something there.

I would be interested in answers to the question regardless of whether they go through some analog of the Fourier transform. Also, I don't mind various restrictions such as making $n$ a power of $2$, replacing $\mathbb{R}$ with $\mathbb{Q}$, removing $\infty$ from the definition of the semiring, etc. Really anything on this theme would be helpful. Also any suggestions for better tags would be appreciated; perhaps this is a well-studied area I'm not aware of.

This question arises from an application to graphical models in probability theory, but I have abstracted that part out so only algebra remains. Let $\mathbb{R}$ denote standard field of real numbers and $\mathcal{R} = (\mathbb{R}\cup\{\infty\},\min,+)$ the tropical semiring. Let $\mathbb{Z}_n$ denote the cyclic group of order $n$.

Elements of the group ring $\mathbb{R}\mathbb{Z}_n$ are tuples $(x_0,\ldots,x_{n-1})$ and multiplication of these corresponds to discrete cyclic convolution. The Fast Fourier Transform gives an embedding $\mathbb{R}\mathbb{Z}_n\to\mathbb{C}^n$ (with elementwise sum and product). The FFT and its inverse can be computed in $O(n\log n)$ arithmetic operations, so elements of $\mathbb{R}\mathbb{Z}_n$ can be multiplied in $O(n\log n)$ arithmetic operations.

Define the group semiring $\mathcal{R}\mathbb{Z}_n$ in an analogous way. The product of $x = (x_0,\ldots, x_{n-1})$ and $y = (y_0,\ldots,y_{n-1})$ in this semiring is given by $(x\cdot y)_k = \min _{j \in \mathbb{Z}_n} (x_j + y_{k-j})$. This operation could perhaps be called "discrete cyclic infimal convolution" by analogy with the notion of infimal convolution in convex analysis. I'm not sure whether there is a more standard name -- this one does not pop up in quick google searches.

The naive way of computing a discrete infimal convolution uses $O(n^2)$ operations, just as the naive method for computing a standard cyclic convolution. My question is: is there a way to compute this "discrete cyclic infimal convolution" in $O(n\log n)$ arithmetic operations?

In convex analysis, there is an analog of the Fourier transform which turns infimal convolution into pointwise addition: the convex conjugate (or Fenchel or Legendre transformation). However, this operation only behaves nicely for convex functions, so it is not clear to me how one would translate it to an equivalent tool for $\mathcal{R}\mathbb{Z}_n$, but perhaps there is something there.

I would be interested in answers to the question regardless of whether they go through some analog of the Fourier transform. Also, I don't mind various restrictions such as making $n$ a power of $2$, replacing $\mathbb{R}$ with $\mathbb{Q}$, removing $\infty$ from the definition of the semiring, etc. Really anything on this theme would be helpful. Also any suggestions for better tags would be appreciated; perhaps this is a well-studied area I'm not aware of.