# A logarithmic uncertainty principle for functions with radial symmetry

Jacopo Bellazzini  Jacopo Bellazzini
Dipartimento di Matematica
Università di Pisa
t Largo B. Pontecorvo 5, 56100 Pisa, Italy  and  Matteo Nesi  Matteo Nesi
Scuola Normale Superiore
Piazza dei Cavalieri 7, 56100 Pisa, Italy

###### Abstract.

In this note, we prove a new uncertainty principle for functions with radial
symmetry by differentiating a radial version of the Stein-Weiss inequality.
The difficulty is to prove the differentiability in the limit of the best
constant that, unlike the general case, it is not known.

###### Key words and phrases:

Logarithmic uncertainty, Stein-Weiss inequality, fractional Sobolev spaces

###### 2010 Mathematics Subject Classification:

39B62 ,46E35, 46B70

J. B. is partially supported by project PRIN 2020XB3EFL by the Italian
Ministry of Universities and Research and by the University of Pisa, Project
PRA 2022 11.

##  1\. Introduction

In this note, we will be differentiating inequalities, so we start by
summarizing the general reasoning scheme. Let us suppose that we are given a
family of inequalities

$F_{t}\leq k_{t}G_{t}$

parametrized by $t>0$. We choose to keep separate the families $F_{t},G_{t}$
from the family $k_{t}$, since in later applications $F_{t},G_{t}$ will be
given by some functionals computed on a fixed function $f$, while $k_{t}$ are
the (optimal) constants in the inequalities. Suppose further that

  * •

the functions $F_{t},G_{t},k_{t}$ are actually defined and differentiable for
$t\geq 0$ ;

  * •

$F_{0}=k_{0}G_{0}$.

Then we can write

$\frac{F_{t}-F_{0}}{t}\leq\frac{k_{t}G_{t}-k_{0}G_{0}}{t}$

and passing to the limit for $t\to 0^{+}$ we get

(1) $\partial_{t}F_{t}|_{t=0}\leq
G_{0}\partial_{t}k_{t}|_{t=0}+k_{0}\partial_{t}G_{t}|_{t=0}.$

These computations will be carried out, in each case, for functions in a
suitable class which allows differentiation under the integral sign; in our
case it is convenient to consider the Schwartz class
$\mathcal{S}(\mathbb{R}^{d})$, which is made of regular and decaying functions
and is well-behaved with respect to the Fourier transform.

For a first example, we start with the Hardy-Littlewood-Sobolev inequality

$\left|\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}\frac{f(x)g(y)}{|x-y|^{\lambda}}\mathop{}\\!\mathrm{d}x\mathop{}\\!\mathrm{d}y\right|\lesssim||f||_{p}||g||_{q},$

which, in the case $f=g\geq 0$ ($p=q$ and $0<\lambda<d$), becomes

$\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}\frac{f(x)f(y)}{|x-y|^{\lambda}}\mathop{}\\!\mathrm{d}x\mathop{}\\!\mathrm{d}y\leq
k_{\lambda}||f||^{2}_{\frac{2d}{2d-\lambda}},$

where

$k_{\lambda}=\pi^{\frac{\lambda}{2}}\frac{\Gamma(\frac{d}{2}-\frac{\lambda}{2})}{\Gamma(d-\frac{\lambda}{2})}\left(\frac{\Gamma(\frac{d}{2})}{\Gamma(d)}\right)^{-1+\frac{\lambda}{d}}$

and the inequality becomes an _equality_ when $\lambda=0.$ By observing that

$\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}\lambda}|x-y|^{-\lambda}|_{\lambda=0}=-\log|x-y|$

and following the above reasoning scheme, we get the logarithmic Hardy-
Littlewood-Sobolev inequality (cf. [6]):

$\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}\\!-\log|x-y|\
f(x)f(y)\mathop{}\\!\mathrm{d}x\mathop{}\\!\mathrm{d}y\leq\frac{1}{d}\int_{\mathbb{R}^{d}}f\log
f\mathop{}\\!\mathrm{d}x+C_{0},$

for regular $f\geq 0$ with $||f||_{1}=1$, where
$C_{0}=\partial_{\lambda}k_{\lambda}|_{\lambda=0}$.

Also, a quantity similar to the LHS of the previous inequality can be
estimated differentiating the sharp Young inequality: as in [7] (ch. 8, p.
223), we find, for any $a>0$, the logarithmic Sobolev inequality in
$\mathbb{R}^{d}$

$\int_{\mathbb{R}^{d}}|f|^{2}\log|f|\mathop{}\\!\mathrm{d}x\leq\frac{a^{2}}{\pi}\int_{\mathbb{R}^{d}}|\nabla
f|^{2}\mathop{}\\!\mathrm{d}x-d(1+\log a),$

which holds for every $f\in H^{1}(\mathbb{R}^{d})$ with
$\left\|f\right\|_{2}=1$.

Concerning the Fourier transform, a classical inequality is the
Hausdorff-Young inequality for $1\leq p\leq 2$

$||\widehat{f}||_{p^{\prime}}\lesssim||f||_{p},$

from which Beckner [2] derived a logarithmic uncertainty principle for
$f\in\mathcal{S}(\mathbb{R}^{d})$ with $\left\|f\right\|_{2}=1$

$\int_{\mathbb{R}^{d}}|f|^{2}\log|f|\mathop{}\\!\mathrm{d}x+\int_{\mathbb{R}^{d}}|\widehat{f}|^{2}\log|\widehat{f}|\mathop{}\\!\mathrm{d}\xi\leq\frac{d}{2}(\log(2)-1)<0.$

So far, we have examples in which we get inequalities involving logarithmic
terms, in the form of $\log(f)$ or the kernel $\log|x-y|$. Now we recall three
families of inequalities which give also logarithmic weights in physical
$(\log|x|)$ and Fourier $(\log|\xi|)$ domains. These are Sobolev, Hardy and
Stein-Weiss inequalities, the latter being a generalization of the first two
”endpoint” inequalities. The results of the differentiation are summarized as
follows: the Sobolev and Hardy inequalities give, respectively,
($\left\|f\right\|_{2}=1$) [3]

$\displaystyle||f||_{\frac{2d}{d-2s}}$
$\displaystyle\lesssim||f||_{\dot{H}^{s}}\ \longrightarrow\
\frac{2}{d}\int_{\mathbb{R}^{d}}|f|^{2}\log|f|\mathop{}\\!\mathrm{d}x\leq\int_{\mathbb{R}^{d}}|\hat{f}|^{2}\log|\xi|\mathop{}\\!\mathrm{d}\xi+c$
$\displaystyle\left\||\cdot|^{-s}f\right\|_{2}$
$\displaystyle\lesssim||f||_{\dot{H}^{s}}\
\longrightarrow\quad-\int_{\mathbb{R}^{d}}|f|^{2}\log|x|\mathop{}\\!\mathrm{d}x\leq\int_{\mathbb{R}^{d}}|\hat{f}|^{2}\log|\xi|\mathop{}\\!\mathrm{d}\xi+c$

and, by interpolating, the Stein-Weiss inequality

$\left\||\cdot|^{-\beta}f\right\|_{p}\lesssim||f||_{\dot{H}^{s}}$

yields (cf. 4)

(2)
$\begin{split}\frac{2(1-t)}{d}\int_{\mathbb{R}^{d}}&|f|^{2}\log|f|\mathop{}\\!\mathrm{d}x-t\int_{\mathbb{R}^{d}}|f|^{2}\log|x|\mathop{}\\!\mathrm{d}x\leq\\\
&\leq\int_{\mathbb{R}^{d}}|\widehat{f}|^{2}\log|\xi|\mathop{}\\!\mathrm{d}\xi+c\end{split}$

for all $t\in[0,1]$. In the above inequalities, $c$ is a constant that differs
from line to line.

The aim of the note is to prove an improvement of the logarithmic Stein-Weiss
inequality (eq. 2) when restricted to radially symmetric functions. We denote
by $\dot{H}_{rad}^{s}(\mathbb{R}^{d})$ the space of radial functions which
belong to $\dot{H}^{s}(\mathbb{R}^{d})$. The starting point is an improvement
of Stein-Weiss inequality for radial functions, which is due to Rubin.

######  Theorem 1 (Rubin inequality, [8], [4], [5]).

Given $f\in\dot{H}_{rad}^{s}(\mathbb{R}^{d})$ with $0\leq s<d/2$ and $p,\beta$
with the relations $(1/0:=+\infty)$

$\displaystyle 2\leq p\leq\frac{2}{(1-2s)_{+}}$
$\displaystyle\beta=s+\frac{d}{p}-\frac{d}{2},$

one has the inequality

$\left\|\ |\cdot|^{-\beta}f\right\|_{p}\leq C(p,s)||f||_{\dot{H}^{s}}.$

######  Remark 2.

The latter theorem is an improvement of Stein-Weiss inequality on radial
functions, meaning that the range of parameters $p$ extends further on the
right and for big values of $p$ even positive exponents $-\beta$ are allowed.

We point out that in 1 the optimal constants $C(p,s)$ are not known, but via
an interpolation argument we get an estimate which is sufficient to carry out
the differentiation, so as to get:

######  Theorem 3.

There exists a constant $c\in\mathbb{R}$ such that, given
$f\in\mathcal{S}(\mathbb{R}^{d})$ radial and with $\left\|f\right\|_{2}=1$

(3)
$\begin{split}2\int_{\mathbb{R}^{d}}|f|^{2}&\log|f|\mathop{}\\!\mathrm{d}x+(d-1)\int_{\mathbb{R}^{d}}|f|^{2}\log|x|\mathop{}\\!\mathrm{d}x\leq\\\
&\leq\int_{\mathbb{R}^{d}}|\widehat{f}|^{2}\log|\xi|\mathop{}\\!\mathrm{d}\xi+c\end{split}$

######  Remark 4.

The argument in the proof holds, in particular, in the restricted range of
parameters $2\leq p\leq 2d/(d-2s)$ or equivalently $0\leq\beta\leq s$. For
this range of exponent, the Rubin inequality holds even for non-radial
functions (thanks to Stein-Weiss inequality) and the differentiation gives,
for any $0\leq t\leq 1$, again

$\frac{2(1-t)}{d}\int_{\mathbb{R}^{d}}|f|^{2}\log|f|\mathop{}\\!\mathrm{d}x\
-\
t\int_{\mathbb{R}^{d}}|f|^{2}\log|x|\mathop{}\\!\mathrm{d}x\leq\int_{\mathbb{R}^{d}}|\widehat{f}|^{2}\log|\xi|\mathop{}\\!\mathrm{d}\xi+c.$

Notice that the relevant difference w.r.t. the radial case is only the sign of
the constant in front of the second term.

######  Remark 5.

Stein-Weiss inequality can be improved in the radial case (Rubin inequality),
while Sobolev and Hardy cannot.

###  1.1. Notations.

$L^{p}(\mathbb{R}^{d})$, with $p\in[1,\infty],$ denote the usual Lebesgue
spaces, $\dot{H}^{s}(\mathbb{R}^{d})$ stands for the usual homogeneous Sobolev
space, namely the space of tempered distribution $u$ over $\mathbb{R}^{d}$,
the Fourier transform of which belongs $L^{1}_{loc}(\mathbb{R}^{d})$ and
satisfies

$||u||_{\dot{H}^{s}(\mathbb{R}^{d})}^{2}=\int_{\mathbb{R}^{d}}|\xi|^{2s}|\widehat{u}|^{2}d\xi<+\infty.$

In this paper, we adopt the following definition for the Fourier Transform:

$\mathcal{F}[f](\xi):=\widehat{f}(\xi):=(2\pi)^{-d/2}\int_{\mathbb{R}^{d}}f(x)\
e^{-i\xi\cdot x}\mathop{}\\!\mathrm{d}x,$

so that, defining

$\widehat{|D|f}:=|\xi|\widehat{f},$

one has

$\left\||D|f\right\|_{2}=\left\|\nabla f\right\|_{2}.$

For references on the properties of homogeneous and nonhomogeneous Sobolev
spaces, we refer to [1].

##  2\. Proof of main results

In order to prove the estimate on the growth of the constant of the Rubin
inequality near $s=0$ we need an interpolation result due to Stein, so we
start with a preliminary definition

######  Definition 6.

Let $(M,\mathcal{M},\mu),(N,\mathcal{N},\nu)$ be two $\sigma$-finite measure
spaces and $\\{T_{z}\\}_{z\in\overline{\Sigma}}$ a family of operators defined
on the space of simple functions on $M$ and taking values in the space of
measurable functions on $N$. The family of operators is said to be
_admissible_ if, for every couple of simple functions $f,g$ defined on $M,N$
respectively, the function

$z\mapsto\langle\overline{T_{z}f},g\rangle:=\int_{N}T_{z}f\
g\mathop{}\\!\mathrm{d}\nu$

is holomorphic in $\Sigma:=(0,1)\times i\mathbb{R}\subset\mathbb{C}$ and
continuous up to the boundary and for some $a<\pi$

$\sup_{z\in\overline{\Sigma}}\ e^{-a|y|}\log|\langle
T_{z}f,g\rangle|<+\infty.$

######  Theorem 7 (Stein interpolation, [9],[10]).

Given $p_{0},p_{1},q_{0},q_{1}\in[1,+\infty]$ and an admissable family of
operators $\\{T_{z}\\}_{z\in\overline{\Sigma}}$ satisfying

$||T_{iy}||_{L^{p_{0}}\to L^{q_{0}}}\leq
M_{0}(y),\quad||T_{1+iy}||_{L^{p_{1}}\to L^{q_{1}}}\leq M_{1}(y)$

and the growth condition

$\sup_{y\in\mathbb{R}}\ e^{-a|y|}\log M_{j}(y)<+\infty\quad\text{ for }j=0,1$

with $a<\pi$, it holds

$||T_{t}||_{L^{p_{t}}\to L^{q_{t}}}\leq M_{t},$

for $0<t<1$, where

$\displaystyle M_{t}:=\int_{\mathbb{R}}\frac{M_{0}(y)}{\cosh(\pi y)-\cos(\pi
t)}+\frac{M_{1}(y)}{\cosh(\pi y)+\cos(\pi t)}\mathop{}\\!\mathrm{d}y,$
$\displaystyle\frac{1}{p_{t}}:=\frac{1-t}{p_{0}}+\frac{t}{p_{1}},$
$\displaystyle\frac{1}{q_{t}}:=\frac{1-t}{q_{0}}+\frac{t}{q_{1}}.$

We are interested in the case where the functions $M_{0},M_{1}$ can be chosen
to be bounded; the previous theorem becomes:

######  Corollary 8 (Stein interpolation - weak version).

Given $p_{0},p_{1},q_{0},q_{1}\in[1,+\infty]$ and an admissable family of
operators $\\{T_{z}\\}_{z\in\overline{\Sigma}}$ satisfying

$||T_{iy}||_{L^{p_{0}}\to L^{q_{0}}}\leq M_{0},\quad||T_{1+iy}||_{L^{p_{1}}\to
L^{q_{1}}}\leq M_{1},$

it holds

$||T_{t}||_{L^{p_{t}}\to L^{q_{t}}}\leq M_{t},$

for $0<t<1$, where

$\displaystyle M_{t}:=M_{0}^{1-t}M_{1}^{t},$
$\displaystyle\frac{1}{p_{t}}:=\frac{1-t}{p_{0}}+\frac{t}{p_{1}},$
$\displaystyle\frac{1}{q_{t}}:=\frac{1-t}{q_{0}}+\frac{t}{q_{1}}.$

######  Remark 9.

In the following, we will need to interpolate some inequalities that hold only
for functions belonging to a proper subspace of an $L^{p}$ space, for example
only for radial functions, so we notice that if $\mathcal{G}$ is a family of
simple functions on $M$ such that the hypotheses of one of the above
interpolation theorems hold for $f\in\mathcal{G}$, for instance

$||T_{j+iy}f||_{q_{j}}\leq M_{j}(y)||f||_{p_{j}}\quad(j=0,1)\quad\forall
f\in\mathcal{G},$

then the corresponding interpolation result states that

$||T_{t}f||_{q_{t}}\leq M_{t}||f||_{p_{t}}$

for every $f$ in the closure of $\mathcal{G}$ as a subset of $L^{p_{t}}(\mu)$.

######  Lemma 10.

If $C(p,s)$ is the optimal constant in Rubin’s inequality and $0\leq s\leq
s_{1}<d/2$, then we have the estimate

$C(p_{\theta},s)\leq C(p_{1},s_{1})^{s/s_{1}},$

where $\theta=s/s_{1}$ and $1/p_{\theta}=(1-\theta)/2+\theta/p_{1}$.

###### Proof.

Setting $f=|D|^{-s}\varphi$, the Rubin inequality reads

$\left\||\cdot|^{-\beta}\ |D|^{-s}\varphi\right\|_{p}\leq
C(p,s)||\varphi||_{2},$

so we are led to consider the family of operators

$\widetilde{T}_{s,\beta}:\varphi\mapsto|\cdot|^{-\beta}\ |D|^{-s}\varphi.$

If $s_{1},p_{1}$ are fixed, to apply the interpolation result we use
$\theta=s/s_{1}$ as a parameter and we set

$\frac{1}{p_{\theta}}=\frac{1-\theta}{2}+\frac{\theta}{p_{1}}$

and, by the relation between the parameters in Rubin inequality, we have

$\beta_{\theta}=\theta
s_{1}+\frac{d}{p_{\theta}}-\frac{d}{2}=\theta\left(\frac{d}{p_{1}}-\frac{d}{2}+s_{1}\right)=\theta\beta_{1}.$

Now we have a new family of operators that depend on a single parameter

$T_{\theta}:\varphi\mapsto|\cdot|^{-\beta_{\theta}}\
|D|^{-s_{\theta}}\varphi=|\cdot|^{-\beta_{1}\theta}\
|D|^{-s_{1}\theta}\varphi$

that can be defined on the whole strip $\overline{\Sigma}$. On the left line
$\\{x=0\\}$ we have

$||T_{iy}\varphi||_{2}=\left\||D|^{-s_{1}iy}\varphi\right\|_{2}=\left\||\cdot|^{-s_{1}iy}\widehat{\varphi}\right\|_{2}=||\varphi||_{2}$

so that

$||T_{iy}||_{L^{2}\to L^{2}}\leq 1.$

On the left line $\\{x=1\\}$

$\displaystyle||T_{1+iy}\varphi||_{p_{1}}$
$\displaystyle=\left\||\cdot|^{-\beta_{1}(1+iy)}|D|^{-s_{1}(1+iy)}\varphi\right\|_{p_{1}}=$
$\displaystyle=\left\||\cdot|^{-\beta_{1}}|D|^{-s_{1}}\left(|D|^{-s_{1}iy}\varphi\right)\right\|_{p_{1}}$

and applying Rubin’s inequality

$||T_{1+iy}\varphi||_{p_{1}}\leq
C(p_{1},s_{1})\left\||D|^{-s_{1}iy}\varphi\right\|_{2}=C(p_{1},s_{1})||\varphi||_{2}.$

Given $\varphi,\psi$ simple functions,

$h(z):=\langle\overline{T_{z}\varphi},\psi\rangle=\int_{\mathbb{R}^{d}}|x|^{-\beta_{1}z}\
|D|^{-s_{1}z}\varphi(x)\ \psi(x)\mathop{}\\!\mathrm{d}x$

is a continuous function on $\overline{\Sigma}$ and holomorphic in $\Sigma$;
indeed consider the two variable function

$\displaystyle H(z_{1},z_{2})$
$\displaystyle:=\int_{\mathbb{R}^{d}}|x|^{-\beta_{1}z_{1}}\
|D|^{-s_{1}z_{2}}\varphi(x)\ \psi(x)\mathop{}\\!\mathrm{d}x=$
$\displaystyle=\int_{\mathbb{R}^{d}}\mathcal{F}\left[|x|^{-\beta_{1}z_{1}}\psi(x)\right](\xi)\
|\xi|^{-s_{1}z_{2}}\widehat{\varphi}(\xi)\mathop{}\\!\mathrm{d}\xi.$

The first expression for $H$ shows that, fixing $z_{2}$, $\frac{\partial
H(z_{1},z_{2})}{\partial\bar{z}_{1}}=0$, while the second form gives, $z_{1}$
being fixed, $\frac{\partial H(z_{1},z_{2})}{\partial\bar{z}_{2}}=0$. Hence
$H$ is holomorphic in $\Sigma\times\Sigma$ (Osgood’s Lemma) and

$z\mapsto H(z,z)=h(z)$

is a composition of holomorphic functions, so it is holomorphic itself.
Moreover, the function $h$ is bounded on the strip, since

$\displaystyle|h(z)|$
$\displaystyle=|\langle|D|^{-s_{1}\bar{z}}\overline{\varphi},|\cdot|^{-\beta_{1}\bar{z}}\psi\rangle|=|\langle|\cdot|^{-s_{1}\bar{z}}\widehat{\overline{\varphi}},\mathcal{F}(|\cdot|^{-\beta_{1}\bar{z}}\psi))\rangle|\leq$
$\displaystyle\leq|\langle|\cdot|^{-s_{1}x}\widehat{\overline{\varphi}},\mathcal{F}(|\cdot|^{-\beta_{1}\bar{z}}\psi))\rangle|=|\langle|D|^{-s_{1}x}\overline{\varphi},|\cdot|^{-\beta_{1}\bar{z}}\psi\rangle|\leq$
$\displaystyle\leq|\langle|D|^{-s_{1}x}\overline{\varphi},|\cdot|^{-\beta_{1}x}\psi\rangle|=|\langle\overline{T_{x}\varphi},\psi\rangle=|h(x)|,$

where we have used repeatedly Plancherel identity. This proves that $|h|$ is
bounded on the strip if and only if it is bounded in $[0,1]$; by continuity,
the function $|h|$ is indeed bounded there. Thus we apply Stein interpolation
to get

$||T_{\theta}\varphi||_{p_{\theta}}\leq\left(C(p_{1},s_{1})\right)^{\theta}||\varphi||_{2},$

which means

$\left\||\cdot|^{-\beta_{1}s/s_{1}}|D|^{-s}\varphi\right\|_{p_{\theta}}\leq\left(C(p_{1},s_{1})\right)^{\theta}||\varphi||_{2},$

for every $\varphi\in L_{rad}^{2}(\mathbb{R}^{d})$ and substituting back
$\varphi=|D|^{s}f$

$\left\||\cdot|^{-\beta_{1}s/s_{1}}f\right\|_{p_{\theta}}\leq\left(C(p_{1},s_{1})\right)^{\theta}||f||_{\dot{H}^{s}}$

for every
$f\in|D|^{-s}(L_{rad}^{2}(\mathbb{R}^{d}))=\dot{H}_{rad}^{s}(\mathbb{R}^{d})$.
∎

###### Proof of Main Theorem.

We start by differentiating all the relevant quantities: for the weighted
$L^{p}$ norm

$\displaystyle\partial_{p}\left\||\cdot|^{-\beta}f\right\|_{p}=\partial_{p}\left(\left\||\cdot|^{-\beta}f\right\|_{p}^{p}\right)^{1/p}=$
$\displaystyle=\left\||\cdot|^{-\beta}f\right\|_{p}\partial_{p}\left(\frac{1}{p}\log\left(\left\||\cdot|^{-\beta}f\right\|_{p}^{p}\right)\right)=$
$\displaystyle=\left\||\cdot|^{-\beta}f\right\|_{p}\left(-\frac{1}{p^{2}}\log\left(\left\||\cdot|^{-\beta}f\right\|_{p}^{p}\right)+\frac{1}{p}\frac{\int_{\mathbb{R}^{d}}\partial_{p}\left(|f|^{p}|x|^{-\beta
p}\right)\mathop{}\\!\mathrm{d}x}{\left\||\cdot|^{-\beta}f\right\|_{p}^{p}}\right)$

and

$\displaystyle\partial_{\beta}\left\||\cdot|^{-\beta}f\right\|_{p}=\partial_{\beta}\left(\left\||\cdot|^{-\beta}f\right\|_{p}^{p}\right)^{1/p}=$
$\displaystyle=\frac{1}{p}\left(\left\||\cdot|^{-\beta}f\right\|_{p}^{p}\right)^{1/p-1}\partial_{\beta}\left(\left\||\cdot|^{-\beta}f\right\|_{p}^{p}\right)=$
$\displaystyle=\frac{1}{p}\left(\left\||\cdot|^{-\beta}f\right\|_{p}^{p}\right)^{1/p-1}\int_{\mathbb{R}^{d}}|f|^{p}|x|^{-\beta
p}\left(-p\log|x|\right)\mathop{}\\!\mathrm{d}x.$

Computing the above quantities for $p=2,\beta=0$

$\displaystyle\partial_{p}\left\||\cdot|^{-\beta}f\right\|_{p}\Big{|}_{\begin{subarray}{c}{p=2}\\\
{\beta=0}\end{subarray}}=||f||_{2}\left(-\frac{1}{4}\log||f||_{2}^{2}+\frac{1}{2}||f||_{2}^{-2}\int_{\mathbb{R}^{d}}|f|^{2}\log|f|\mathop{}\\!\mathrm{d}x\right)$
$\displaystyle=\frac{1}{2}\int_{\mathbb{R}^{d}}|f|^{2}\log|f|\mathop{}\\!\mathrm{d}x$

and similarly

$\partial_{\beta}\left\||\cdot|^{-\beta}f\right\|_{p}\Big{|}_{\begin{subarray}{c}{p=2}\\\
{\beta=0}\end{subarray}}=-||f||_{2}^{-1}\\!\int_{\mathbb{R}^{d}}|f|^{2}\log|x|\mathop{}\\!\mathrm{d}x=-\int_{\mathbb{R}^{d}}|f|^{2}\log|x|\mathop{}\\!\mathrm{d}x.$

This means that

$\displaystyle\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}s}\left\||\cdot|^{-\beta}f\right\|_{p}|_{s=0}=\frac{\mathop{}\\!\mathrm{d}p}{\mathop{}\\!\mathrm{d}s}|_{s=0}\
\partial_{p}\left\||\cdot|^{-\beta}f\right\|_{p}\Big{|}_{\begin{subarray}{c}{p=2}\\\
{\beta=0}\end{subarray}}+$
$\displaystyle+\frac{\mathop{}\\!\mathrm{d}\beta}{\mathop{}\\!\mathrm{d}s}|_{s=0}\
\partial_{\beta}\left\||\cdot|^{-\beta}f\right\|_{p}\Big{|}_{\begin{subarray}{c}{p=2}\\\
{\beta=0}\end{subarray}}=$
$\displaystyle=\frac{1}{2}\frac{\mathop{}\\!\mathrm{d}p}{\mathop{}\\!\mathrm{d}s}|_{s=0}\int_{\mathbb{R}^{d}}|f|^{2}\log|f|\mathop{}\\!\mathrm{d}x-\frac{\mathop{}\\!\mathrm{d}\beta}{\mathop{}\\!\mathrm{d}s}|_{s=0}\int_{\mathbb{R}^{d}}|f|^{2}\log|x|\mathop{}\\!\mathrm{d}x.$

Now we choose $s_{1},p_{1},\beta_{1}$ in the permitted range of values and,
referring to lemma 10, define

$p(s):=p_{s/s_{1}}\quad\text{ and }\quad\beta(s):=\beta_{s/s_{1}}.$

With this choice

$\displaystyle\frac{\mathop{}\\!\mathrm{d}p}{\mathop{}\\!\mathrm{d}s}|_{s=0}=\frac{4}{s_{1}}\left(\frac{1}{2}-\frac{1}{p_{1}}\right)=\frac{4}{d}\left(1-\frac{\beta_{1}}{s_{1}}\right)$
$\displaystyle\frac{\mathop{}\\!\mathrm{d}\beta}{\mathop{}\\!\mathrm{d}s}|_{s=0}=1-\frac{d}{s_{1}}\left(\frac{1}{2}-\frac{1}{p_{1}}\right)=\frac{\beta_{1}}{s_{1}}.$

Since we are considering the Rubin inequality with a constant given by lemma
10, we need to compute

$\partial_{s}\left(C(p_{1},s_{1})\right)^{s/s_{1}}|_{s=0}=\frac{1}{s_{1}}\log
C(p_{1},s_{1})$

and recalling that

$\partial_{s}||f||_{\dot{H}^{s}}|_{s=0}=\int_{\mathbb{R}^{d}}|\widehat{f}|^{2}\log|\xi|\mathop{}\\!\mathrm{d}\xi$

we get the inequality

(4)
$\begin{split}\frac{2}{d}\left(1-\frac{\beta_{1}}{s_{1}}\right)\int_{\mathbb{R}^{d}}|f|^{2}\log|f|\mathop{}\\!\mathrm{d}x-\frac{\beta_{1}}{s_{1}}\int_{\mathbb{R}^{d}}|f|^{2}\log|x|\mathop{}\\!\mathrm{d}x\leq\\\
\leq\frac{1}{s_{1}}\log
C(p_{1},s_{1})+\int_{\mathbb{R}^{d}}|\widehat{f}|^{2}\log|\xi|\mathop{}\\!\mathrm{d}\xi.\end{split}$

In particular we can choose the values $p_{1}=2/(1-2s_{1})$ and
$\beta_{1}=s_{1}(1-d)$ to get

$2\int_{\mathbb{R}^{d}}|f|^{2}\log|f|\mathop{}\\!\mathrm{d}x+(d-1)\int_{\mathbb{R}^{d}}|f|^{2}\log|x|\mathop{}\\!\mathrm{d}x\leq\int_{\mathbb{R}^{d}}|\widehat{f}|^{2}\log|\xi|\mathop{}\\!\mathrm{d}\xi+c$

for some $c\in\mathbb{R}$. ∎

## References

  * [1] H. Bahouri, J.Y. Chemin, and R. Danchin.  Fourier Analysis and Nonlinear Partial Differential Equations.  Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2011.
  * [2] William Beckner.  Inequalities in fourier analysis.  Annals of Mathematics, 102(1):159–182, 1975.
  * [3] William Beckner.  Pitt’s inequality and the uncertainty principle.  Proceedings of the American Mathematical Society, 123(6):1897–1905, 1995.
  * [4] Jacopo Bellazzini, Rupert L Frank, and Nicola Visciglia.  Maximizers for gagliardo–nirenberg inequalities and related non-local problems.  Mathematische Annalen, 360:653–673, 2014.
  * [5] Jacopo Bellazzini, Marco Ghimenti, Carlo Mercuri, Vitaly Moroz, and Jean Van Schaftingen.  Sharp gagliardo–nirenberg inequalities in fractional coulomb–sobolev spaces.  Transactions of the American Mathematical Society, 370(11):8285–8310, 2018.
  * [6] E. Carlen and M. Loss.  Competing symmetries, the logarithmic hls inequality and onofri’s inequality on sn.  Geometric and functional analysis, 2(1):90–104, 1992.
  * [7] E.H. Lieb and M. Loss.  Analysis.  Crm Proceedings & Lecture Notes. American Mathematical Society, 2001\.
  * [8] B. S. Rubin.  One-dimensional representation, inversion and certain properties of Riesz potentials of radial functions.  Mat. Zametki, 34(4):521–533, 1983.
  * [9] Elias M. Stein.  Interpolation of linear operators.  Transactions of the American Mathematical Society, 83(2):482–492, 1956.
  * [10] Elias M. Stein and Guido Weiss.  Introduction to Fourier Analysis on Euclidean Spaces (PMS-32).  Princeton University Press, 1971.


∎

11institutetext:

# On $-1$-differential uniformity of ternary APN power functions ††thanks: H.
Yan is with School of Mathematics, Southwest Jiaotong University, Chengdu,
610031, China; and is also with Guangxi Key Laboratory of Cryptography and
Information Security, Guilin, 541000, China (email: hdyan@swjtu.edu.cn).

Haode Yan

(Received: date / Accepted: date)

###### Abstract

Very recently, a new concept called multiplicative differential and the
corresponding $c$-differential uniformity were introduced by Ellingsen et al.
A function $F(x)$ over finite field ${\mathrm{GF}}(p^{n})$ to itself is called
$c$-differential uniformity $\delta$, or equivalent, $F(x)$ is differentially
$(c,\delta)$ uniform, when the maximum number of solutions
$x\in{\mathrm{GF}}(p^{n})$ of $F(x+a)-F(cx)=b$,
$a,b,c\in{\mathrm{GF}}(p^{n})$, $c\neq 1$ if $a=0$, is equal to $\delta$. The
objective of this paper is to study the $-1$-differential uniformity of
ternary APN power functions $F(x)=x^{d}$ over ${\mathrm{GF}}(3^{n})$. We
obtain ternary power functions with low $-1$-differential uniformity, and some
of them are almost perfect $-1$-nonlinear.

###### Keywords:

c-differential differential uniformity almost perfect c-nonlinearity

###### MSC:

11T06 94A60

##  1 Introduction

Differential cryptanalysis (BS ; BS93 ) is one of the most fundamental
cryptanalytic approaches targeting symmetric-key primitives. Such a
cryptanalysis approach has attracted a lot of attention because it was
proposed to be the first statistical attack for breaking the iterated block
ciphers BS . The security of cryptographic functions regarding differential
attacks was widely studied in the past 30 years. This type of security is
quantified by the so-called _differential uniformity_ of the substitution box
(S-box) used in the cipher NK . In BCJW , a new type of differential was
proposed. The authors utilized modular multiplication as a primitive
operation, which extends the type of differential cryptanalysis. It is
necessary to start the theoretical analysis of an (output) multiplicative
differential. Motivated by practical differential cryptanalysis, Ellingsen et
al. recently coined a new concept called _multiplicative differential_ and the
corresponding $c$-differential uniformity (EFRST ).

###### Definition 1

Let ${\mathrm{GF}}(p^{n})$ denote the finite field with $p^{n}$ elements,
where $p$ is a prime number and $n$ is a positive integer. For a function $F$
from ${\mathrm{GF}}(p^{n})$ to itself, $a,c\in{\mathrm{GF}}(p^{n})$, the
(multiplicative) $c$ derivative of $F$ with respect to $a$ is define as

${}_{c}D_{a}F(x)=F(x+a)-cF(x),~{}\mathrm{for}~{}\mathrm{all}~{}x.$

For $b\in{\mathrm{GF}}(p^{n})$, let
${}_{c}\Delta_{F}(a,b)=\\#\\{x\in{\mathrm{GF}}(p^{n}):F(x+a)-cF(x)=b\\}$. We
call
${}_{c}\Delta_{F}=\mathrm{max}\\{_{c}\Delta_{F}(a,b):a,b\in{\mathrm{GF}}(p^{n}),\mathrm{and}~{}a\neq
0~{}\mathrm{if}~{}c=1\\}$ the $c$-differential uniformity of F. If
${}_{c}\Delta_{F}=\delta$, then we say $F$ is differentially
$(c,\delta)$-uniform.

If the $c$-differential uniformity of $F$ equals $1$, then $F$ is called a
perfect $c$-nonlinear (P$c$N) function. P$c$N functions over odd
characteristic finite fields are also called $c$-planar functions. If the
$c$-differential uniformity of $F$ is $2$, then $F$ is called an almost
perfect $c$-nonlinear (AP$c$N) function. It is easy to see that, for $c=1$ and
$a\neq 0$, the $c$-differential uniformity becomes the usual differential
uniformity, and the P$c$N and AP$c$N functions become perfect nonlinear (PN)
function and almost perfect nonlinear function (APN) respectively. These
functions are of great significance in both theory and practical applications.
For even characteristic finite fields, APN functions have the lowest
differential uniformity. Known APN functions over even characteristic finite
fields were presented in BD ; D1 ; D2 ; D3 ; G ; JW ; K ; N . For the known
results on PN and APN functions over odd characteristic finite fields, the
readers are referred to CM ; DMMPW ; DO ; DY ; HRS ; HS ; L ; ZW10 ; ZW11 .

Because of the strong resistance to differential attacks and the low
implementation cost in a hardware environment, power function $F(x)=x^{d}$
(i.e., monomials) with low differential uniformity can serve as a good
candidate for the design of S-boxes. Moreover, power functions with low
differential uniformity may also introduce some unsuitable weaknesses within a
cipher BCC ; JaKn ; CoPi ; CaVi . For instance, a differentially $4$-uniform
power function, which is extended affine EA-equivalent to the inverse function
$x\mapsto x^{2^{n}-2}$ over ${\mathrm{GF}}(2^{n})$ with even $n$, is employed
in the AES (advanced encryption standard). A nature question one would ask is
whether the power functions have good $c$-differential properties. In EFRST ,
the authors studied the $c$-differential uniformity of the well-known inverse
function $F(x)=x^{p^{n}-2}$ over ${\mathrm{GF}}(p^{n})$ for both even and odd
prime $p$. It was shown that $F(x)$ is P$c$N when $c=0$, $F(x)$ is AP$c$N with
some conditions of $c$ and $F(x)$ is differentially $(c,3)$-uniform otherwise.
This result illustrates that P$c$N functions can exist for $p=2$. For P$c$N
functions $x^{\frac{3^{k}+1}{2}}$ over ${\mathrm{GF}}(3^{n})$ and $c=-1$, a
sufficient and necessary condition was presented in EFRST . In BT , it was
shown that for odd $p$, $n$ and $c=-1$, $x^{\frac{p^{2}+1}{2}}$ over
${\mathrm{GF}}(p^{n})$ and $x^{p^{2}-p+1}$ over ${\mathrm{GF}}(p^{3})$ are
P$c$N functions. In YMZ , it was proved that the Gold function over even
characteristic finite field is differentially $(c,3)$-uniform for $c\neq 1$.
Some P$c$N and AP$c$N functions were also obtained. Moreover, for
$c$-differential uniformity of power function $F(x)=x^{d}$ over
${\mathrm{GF}}(p^{n})$ with $c\neq 1$, the following lemma was introduced.

######  Lemma 1 (YMZ )

Let $F(x)=x^{d}$ be a power function over ${\mathrm{GF}}(p^{n})$. Then

${}_{c}\Delta_{F}=\mathrm{max}\big{\\{}~{}\\{{{}_{c}\Delta_{F}}(1,b):b\in{\mathrm{GF}}(p^{n})\\}\cup\\{\gcd(d,p^{n}-1)\\}~{}\big{\\}}.$

Table 1: Power functions $F(x)=x^{d}$ over ${\mathrm{GF}}(p^{n})$ with low
$c$-differential uniformity

$p$ | $d$ | condition | ${}_{c}\Delta_{F}$ | References
---|---|---|---|---
any | $2$ | $c\neq 1$ | 2 | EFRST
any | $p^{n}-2$ | $c=0$ | $1$ | EFRST
2 | $2^{n}-2$ |  $c\neq 0$, $\mathrm{Tr_{n}}(c)=\mathrm{Tr_{n}}(c^{-1})=1$ | $2$ | EFRST
2 | $2^{n}-2$ |  $c\neq 0$, $\mathrm{Tr_{n}}(c)=0$ or $\mathrm{Tr_{n}}(c^{-1})=0$ | $3$ | EFRST
odd | $p^{n}-2$ |  $c=4$, $c=4^{-1}$ or $\chi(c^{2}-4c)=\chi(1-4c)=-1$ | $2$ | EFRST
odd | $p^{n}-2$ |  $c\neq 0,4,4^{-1}$, $\chi(c^{2}-4c)$=1 or $\chi(1-4c)=1$ | $3$ | EFRST
3 | $({3^{k}+1})/{2}$ |  $c=-1$, $n/\gcd(k,n)=1$ | 1 | EFRST
odd | $({p^{2}+1})/{2}$ |  $c=-1$, $n$ odd | 1 | BT
odd | $p^{2}-p+1$ |  $c=-1$, $n=3$ | 1 | BT
2 | $2^{k}+1$ |  $c\neq 1$, $\gcd(k,n)=1$ | 3 | YMZ
odd | $p^{k}+1$ |  $1\neq c\in{\mathrm{GF}}(p)$, $\gcd(k,n)=1$ | 2 | YMZ
odd | $(p^{k}+1)/2$ |  $c=-1$, $k/\gcd(k,n)$ is even | $1$ | YMZ
3 | $(3^{k}+1)/2$ |  $c=-1$, $k$ odd, $\gcd(k,n)=1$ | $2$ | YMZ
any | $(2p^{n}-1)/3$ |  $c\neq 1$, $p^{n}\equiv 2(\mathrm{mod}~{}3)$ | $\leq 3$ | YMZ
odd | $(p^{n}+1)/2$ | $c\neq\pm 1$ | $\leq 4$ | YMZ
odd | $(p^{n}+1)/2$ |  $c\neq\pm 1$, $\chi(\frac{1-c}{1+c})=1$, $p^{n}\equiv 1(\mathrm{mod}~{}4)$ | $\leq 2$ | YMZ
$>3$ | $(p^{n}+3)/2$ |  $c=-1$, $p^{n}\equiv 3(\mathrm{mod}~{}4)$ | $\leq 3$ | YMZ
$>3$ | $(p^{n}+3)/2$ |  $c=-1$, $p^{n}\equiv 1(\mathrm{mod}~{}4)$ | $\leq 4$ | YMZ
odd | $(p^{n}-3)/2$ | $c=-1$ | $\leq 4$ | YMZ

  * •

$\mathrm{Tr_{n}}(\cdot)$ denotes the absolute trace mapping from
${\mathrm{GF}}(2^{n})$ to ${\mathrm{GF}}(2)$.

  * •

$\chi(\cdot)$ denotes the quadratic multiplicative character on
${\mathrm{GF}}(p^{n})^{*}$.

Table 2: Results in this paper $p$ | $d$ | condition | ${}_{c}\Delta_{F}$
---|---|---|---
3 | $(3^{\frac{n+1}{2}}-1)/2$ |  $c=-1$, $n\equiv 1(\mathrm{mod}~{}4)$ | $\leq 2$
3 | $(3^{\frac{n+1}{2}}-1)/2+(3^{n}-1)/2$ |  $c=-1$, $n\equiv 3(\mathrm{mod}~{}4)$ | $\leq 2$
3 | $(3^{n+1}-1)/8$ |  $c=-1$, $n\equiv 1(\mathrm{mod}~{}4)$ | $\leq 2$
3 | $(3^{n+1}-1)/8+(3^{n}-1)/2$ |  $c=-1$, $n\equiv 3(\mathrm{mod}~{}4)$ | $\leq 2$
3 | $(3^{\frac{n+1}{2}}-1)/2$ |  $c=-1$, $n\equiv 3(\mathrm{mod}~{}4)$ | $\leq 4$
3 | $(3^{\frac{n+1}{2}}-1)/2+(3^{n}-1)/2$ |  $c=-1$, $n\equiv 1(\mathrm{mod}~{}4)$ | $\leq 4$
3 | $(3^{n+1}-1)/8$ |  $c=-1$, $n\equiv 3(\mathrm{mod}~{}4)$ | $\leq 4$
3 | $(3^{n+1}-1)/8+(3^{n}-1)/2$ |  $c=-1$, $n\equiv 1(\mathrm{mod}~{}4)$ | $\leq 4$
3 | ${(3^{\frac{n+1}{4}}-1)(3^{\frac{n+1}{2}}+1)}$ |  $c=-1$, $n\equiv 3(\mathrm{mod}~{}4)$ | $\leq 4$
3 | $(3^{n}+1)/4+(3^{n}-1)/2$ |  $c=-1$, $n$ odd | $\leq 4$

As summarized in Table 1, $c=-1$ is a very special case and sometimes the
$-1$-differential uniformity is lower than $c$-differential uniformity for
other $c\in{\mathrm{GF}}(p^{n})$. The perfect $-1$-nonlinear function was also
called quasi-planar function BT . In this paper, we study the
$-1$-differential uniformity of $F(x)$ when $F(x)$ is a ternary APN power
function. Lemma 1 indicates that to determine the $-1$-differential uniformity
of power functions, the following $-1$-differential equation needs to be
studied.

$\Delta(x)=(x+1)^{d}+x^{d}=b.$

Let $\delta(b)=\\#\\{x\in{\mathrm{GF}}(3^{n})~{}|~{}\Delta(x)=b\\}$. The
maximum value of $\\{\delta(b)~{}|~{}b\in{\mathrm{GF}}(3^{n})\\}$ plays an
important role in studying the $-1$-differential uniformity of $F(x)$. In the
rest of this paper, we consider several classes of ternary APN power
functions. It turns out that they are with low $-1$-differential uniformity,
and some of them are almost perfect $-1$-nonlinear. The results in this paper
are shown in Table 2I.

##  2 $-1$-differential uniformity of $x^{\frac{3^{\frac{n+1}{2}}-1}{2}}$ over
${\mathrm{GF}}(3^{n})$

In this section, let $F(x)=x^{d}$ be a power function over
${\mathrm{GF}}(3^{n})$, where $n\equiv 1(\mathrm{mod}~{}4)$ and
$d=\frac{1}{2}(3^{\frac{n+1}{2}}-1)$. It was proved in DMMPW  that $F(x)$ is
an APN function. We consider the $-1$-differential uniformity of $F(x)$ as
follows.

###### Theorem 2.1

Let $F(x)=x^{d}$ be a power function over ${\mathrm{GF}}(3^{n})$, where
$n\equiv 1(\mathrm{mod}~{}4)$ and $d=\frac{1}{2}(3^{\frac{n+1}{2}}-1)$. We
have ${}_{-1}\Delta_{F}\leq 2$.

###### Proof

Let $m=\frac{n+1}{2}$. Note that $2(3^{m}+1)d-3(3^{n}-1)=2$ and $d$ is odd
when $n\equiv 1(\mathrm{mod}~{}4)$, then $\gcd(d,3^{n}-1)=1$, i.e., $F(x)$ is
a permutation on ${\mathrm{GF}}(3^{n})$. For $b\in{\mathrm{GF}}(3^{n})$, we
consider the $-1$-differential equation

$\Delta(x)=(x+1)^{d}+x^{d}=b.$ (1)

Let $u_{x+1}=(x+1)^{d}$ and $u_{x}=x^{d}$. For $x\neq 0$, note that

$u^{3^{m}+1}_{x}=x^{\frac{3^{n+1}-1}{2}}=\chi(x)x.$ (2)

Herein and hereafter, let $\chi$ denote the quadratic multiplicative character
on ${\mathrm{GF}}(3^{n})^{*}$. Let
$x\in{\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$ be a solution of (1) for fixed
$b\in{\mathrm{GF}}(3^{n})$, then $u_{x},u_{x+1}\neq 0$. Taking the
$(3^{m}+1)$th power on both sides of $u_{x+1}=-u_{x}+b$, we have

$bu^{3^{m}}_{x}+b^{3^{m}}u_{x}=-\chi(x+1)(x+1)+\chi(x)x+b^{3^{m}+1}.$ (3)

For equation (3), we distinguish the following four cases.

Case I. $\chi(x+1)=\chi(x)=1$.

In this case, we have $bu^{3^{m}}_{x}+b^{3^{m}}u_{x}=b^{3^{m}+1}-1$ from (3).
Since the mapping $u_{x}\mapsto bu^{3^{m}}_{x}+b^{3^{m}}u_{x}$ is bijective on
${\mathrm{GF}}(3^{n})$, we can find a unique $u_{x}$. Because $F(x)$ is a
permutation, a unique $x$ can be found from the $u_{x}$. This case has at most
one solution.

Case II. $\chi(x+1)=\chi(x)=-1$.

This case has at most one solution. The discussion is similar to that of Case
I and we omit it.

Case III. $\chi(x+1)=1,\chi(x)=-1$. From (3), we have
$bu^{3^{m}}_{x}+b^{3^{m}}u_{x}=x+b^{3^{m}+1}-1$ in this case, and then we have

$(u_{x}+b)^{3^{m}+1}=-b^{3^{m}+1}-1$ (4)

by (2). If there are two distinct solutions in this case, namely $x_{3}$ and
$x^{\prime}_{3}$, then $u_{x_{3}}$ and $u_{x^{\prime}_{3}}$ satisfy (4) with
$\chi(x_{3}+1)=\chi(x^{\prime}_{3}+1)=1$ and
$\chi(x_{3})=\chi(x^{\prime}_{3})=-1$. Consequently
$(u_{x_{3}}+b)^{3^{m}+1}=(u_{x^{\prime}_{3}}+b)^{3^{m}+1}$ can be obtained
from (4). Then we have $u_{x_{3}}+b=-(u_{x^{\prime}_{3}}+b)$ since
$\gcd(3^{m}+1,3^{n}-1)=2$ and $x_{3}\neq x^{\prime}_{3}$, which leads to
$u_{x_{3}}=b-u_{x^{\prime}_{3}}=u_{x^{\prime}_{3}+1}$. However, the above
conclusion contradicts to $\chi(u_{x_{3}})=\chi(x_{3})=-1$ and
$\chi(u_{x^{\prime}_{3}+1})=\chi(x^{\prime}_{3}+1)=1$. We conclude that Case
III has at most one solution.

Case IV. $\chi(x+1)=-1,\chi(x)=1$. In this case we have
$bu^{3^{m}}_{x}+b^{3^{m}}u_{x}=-x+b^{3^{m}+1}+1$ from (3), and then

$(u_{x}+b)^{3^{m}+1}=-b^{3^{m}+1}+1$ (5)

by (2). Similar to Case III, we can obtain that this case has at most one
solution.

Next we will prove that for fixed $b$, (1) cannot have solution in Case I and
Case II simultaneously. Otherwise, suppose that $x_{1}$ and $x_{2}$ are
solutions of (1) in Case I and Case II with $\chi(x_{1}+1)=\chi(x_{1})=1$ and
$\chi(x_{2}+1)=\chi(x_{2})=-1$ respectively. Then we have
$bu^{3^{m}}_{x_{1}}+b^{3^{m}}u_{x_{1}}=b^{3^{m}+1}-1$ and
$bu^{3^{m}}_{x_{2}}+b^{3^{m}}u_{x_{2}}=b^{3^{m}+1}+1$, where $u_{x_{1}}$ and
$u_{x_{2}}$ we defined before. Now we have
$b(u_{x_{1}}+u_{x_{2}})^{3^{m}}+b^{3^{m}}(u_{x_{1}}+u_{x_{2}})=-b^{3^{m}+1}$
and the consequent $u_{x_{1}}+u_{x_{2}}=b$. From (1), we can obtain
$u_{x_{2}}=u_{x_{1}+1}$, which contradicts to $\chi(u_{x_{2}})=\chi(x_{2})=-1$
and $\chi(u_{x_{1}+1})=\chi(x_{1}+1)=1$. Therefore, we conclude that (1) has
at most one solution in Cases I and II for fixed $b\in{\mathrm{GF}}(3^{n})$.

Then we prove that for fixed $b$, (1) cannot have solution in Case III and
Case IV simultaneously. Otherwise, suppose that $x_{3}$ and $x_{4}$ are
solutions of (1) in Case III and Case IV with $\chi(x_{3}+1)=1$,
$\chi(x_{3})=-1$ and $\chi(x_{4}+1)=-1,\chi(x_{4})=1$ respectively. Then
$x_{3}$ and $x_{4}$ satisfy (4) and (5) respectively. By the sum of (4) and
(5), we have

$(u_{x_{3}}+b)^{3^{m}+1}+(u_{x_{4}}+b)^{3^{m}+1}=b^{3^{m}+1}.$ (6)

Taking the $3^{m}$th power on both sides of (6), we have

$(u_{x_{3}}+b)^{3^{m}+3}+(u_{x_{4}}+b)^{3^{m}+3}=b^{3^{m}+3}$ (7)

since $3^{m}(3^{m}+1)=3^{n+1}+3^{m}=3^{m}+3+3(3^{n}-1)$. From (6) and (7), we
have
$(u_{x_{3}}+b)^{3^{m}+3}+(u_{x_{4}}+b)^{3^{m}+3}=b^{2}(u_{x_{3}}+b)^{3^{m}+1}+b^{2}(u_{x_{4}}+b)^{3^{m}+1}$,
that is

$-(u_{x_{3}}+b)^{3^{m}+1}u_{x_{3}}(b-u_{x_{3}})=(u_{x_{4}}+b)^{3^{m}+1}u_{x_{4}}(b-u_{x_{4}}).$
(8)

Note that $b-u_{x_{3}}=u_{x_{3}+1}$ and $b-u_{x_{4}}=u_{{x_{4}}+1}$, the left-
hand side of (8) is a square element and the right-hand side of (8) is a
nonsquare element. Then $u_{x_{3}}+b=u_{x_{4}}+b=0$ can be obtained, i.e.
$u_{x_{3}}=u_{x_{4}}$, which contradicts to $\chi(u_{x_{3}})=\chi(x_{3})=-1$
and $\chi(u_{x_{4}})=\chi(x_{4})=1$. We conclude that (1) has at most one
solution in Cases III and IV for fixed $b\in{\mathrm{GF}}(3^{n})$.

From the above discussions, (1) has at most two solutions in
${\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$. One can be easily calculate that
$\Delta(0)=1$ and $\Delta(-1)=-1$. For $b=1$ and $b=-1$, it can be verified
that $\Delta(x)=1$ and $\Delta(x)=-1$ has no solution in
${\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$, i,e, $\delta(1)=\delta(-1)=1$. Then
we obtain $\delta(b)\leq 2$ for any $b$, which leads to ${}_{-1}\Delta_{F}\leq
2$ by Lemma 1 and $\gcd(d,3^{n}-1)=1$ .

For $n\equiv 3(\mathrm{mod}~{}4)$, we can also get power functions with low
$-1$-differential uniformity.

###### Theorem 2.2

Let $F(x)=x^{d}$ be a power function over ${\mathrm{GF}}(3^{n})$, where
$n\equiv 3(\mathrm{mod}~{}4)$ and $d=\frac{1}{2}(3^{\frac{n+1}{2}}-1)$. We
have ${}_{-1}\Delta_{F}\leq 4$.

###### Proof

The proof is similar to that of Theorem 2.1. We give a sketch here. In this
case, $\gcd(d,3^{n}-1)=2$. With the notation we used before, equations (1),
(2) and (3) also hold. Let $x\in{\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$ be a
solution of (3) for fixed $b\in{\mathrm{GF}}(3^{n})$, four cases are
considered as follows.

Case I. $\chi(x+1)=\chi(x)=1$.

In this case, We have $bu^{3^{m}}_{x}+b^{3^{m}}u_{x}=b^{3^{m}+1}-1$ from (3).
Since the mapping $u_{x}\mapsto bu^{3^{m}}_{x}+b^{3^{m}}u_{x}$ is bijective on
${\mathrm{GF}}(3^{n})$, we can find a unique $u_{x}$. Then a unique $x$ can be
found for $\chi(x)=1$. This case has at most one solution.

Case II. $\chi(x+1)=\chi(x)=-1$.

Similar to Case I, this case has at most one solution.

Case III. $\chi(x+1)=1,\chi(x)=-1$. We have
$bu^{3^{m}}_{x}+b^{3^{m}}u_{x}=x+b^{3^{m}+1}-1$ from (3), and then we have
$(u_{x}+b)^{3^{m}+1}=-b^{3^{m}+1}-1$ by (2). We can obtain two $u_{x}$’s since
$\gcd(d,3^{n}-1)=2$ and the consequent two $x$’s for given $\chi(x)$. This
case has at most two solutions.

Case IV. $\chi(x+1)=-1,\chi(x)=1$.

Similar to Case III, this case has at most two solutions.

One can similarly prove that for fixed $b$, (1) cannot have solution in Case
III and Case IV simultaneously. By discussions as above, we know that (1) has
at most four solutions in ${\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$. We have
$\Delta(0)=\Delta(-1)=1$. For $b=1$, one can easily verify that $\Delta(x)=1$
has no solution in ${\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$, i.e.,
$\delta(1)=2$. Then we obtain $\delta(b)\leq 4$ for any $b$, this leads to
${}_{-1}\Delta_{F}\leq 4$ by Lemma 1 and $\gcd(d,3^{n}-1)=2$.

For $d^{\prime}=d+\frac{3^{n}-1}{2}$, we have the following corollary.

###### Corollary 1

Let $F^{\prime}(x)=x^{d^{\prime}}$ be a power function over
${\mathrm{GF}}(3^{n})$, where $n$ is an odd integer and
$d^{\prime}=\frac{3^{\frac{n+1}{2}}-1}{2}+\frac{3^{n}-1}{2}$. We have
${}_{-1}\Delta_{F^{\prime}}\leq 2$ when $n\equiv 3(\mathrm{mod}~{}4)$ and
${}_{-1}\Delta_{F^{\prime}}\leq 4$ when $n\equiv 1(\mathrm{mod}~{}4)$.

###### Proof

It can be calculated that $\gcd(d^{\prime},3^{n}-1)\leq 2$. First we consider
$n\equiv 3(\mathrm{mod}~{}4)$, i.e., $3n\equiv 1(\mathrm{mod}~{}4)$. By
Theorem 2.1,

$(x+1)^{\frac{3^{\frac{3n+1}{2}}-1}{2}}+x^{\frac{3^{\frac{3n+1}{2}}-1}{2}}=b$
(9)

has at most two solutions in ${\mathrm{GF}}(3^{3n})$ for any
$b\in{\mathrm{GF}}(3^{3n})$. Since
$(3^{n}-1)|\frac{3^{\frac{3n+1}{2}}-1}{2}-d^{\prime}$, equation (9) becomes
$(x+1)^{d^{\prime}}+x^{d^{\prime}}=b$ any $x,b\in{\mathrm{GF}}(3^{n})$.
Therefore, this equation has at most two solutions in ${\mathrm{GF}}(3^{n})$,
i.e., ${}_{-1}\Delta_{F^{\prime}}\leq 2$. The other case can be proved
similarly and we omit the details.

##  3 $-1$-differential uniformity of $x^{\frac{3^{n+1}-1}{8}}$ over
${\mathrm{GF}}(3^{n})$

In this section, let $F(x)=x^{d}$ be a power function over
${\mathrm{GF}}(3^{n})$, where $n\equiv 1(\mathrm{mod}~{}4)$ and
$d=\frac{3^{n+1}-1}{8}$. It was proved in DMMPW  that $F(x)$ is an APN
function. We consider the $-1$-differential uniformity of $F(x)$ as follows.

###### Theorem 3.1

Let $F(x)=x^{d}$ be a power function over ${\mathrm{GF}}(3^{n})$, where
$n\equiv 1(\mathrm{mod}~{}4)$ and $d=\frac{3^{n+1}-1}{8}$. We have
${}_{-1}\Delta_{F}\leq 2$.

###### Proof

Note that $\gcd(d,3^{n}-1)=1$, $F(x)$ is a permutation on
${\mathrm{GF}}(3^{n})$. For $b\in{\mathrm{GF}}(3^{n})$, we consider the
$c$-differential equation

$\Delta(x)=(x+1)^{d}+x^{d}=b.$ (10)

Let $u_{x+1}=(x+1)^{d}$ and $u_{x}=x^{d}$. For $x\neq 0$, note that

$u^{4}_{x}=x^{4d}=\chi(x)x.$ (11)

Let $x\in{\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$ be a solution of (10) for
fixed $b\in{\mathrm{GF}}(3^{n})$, then $u_{x},u_{x+1}\neq 0$. Taking the $4$th
power on both sides of $u_{x+1}=-u_{x}+b$, we have

$bu^{3}_{x}+b^{3}u_{x}=-\chi(x+1)(x+1)+\chi(x)x+b^{4}.$ (12)

For (12), we distinguish the following four cases.

Case I. $\chi(x+1)=\chi(x)=1$.

In this case, we have $bu^{3}_{x}+b^{3}u_{x}=b^{4}-1$ from (12). Since the
mapping $u_{x}\mapsto bu^{3}_{x}+b^{3}u_{x}$ is bijective on
${\mathrm{GF}}(3^{n})$, we can find a unique $u_{x}$. Because $F(x)$ is a
permutation, a unique $x$ can be found from the $u_{x}$. This case has at most
one solution.

Case II. $\chi(x+1)=\chi(x)=-1$.

This case has at most one solution. The discussion is similar to that of Case
I and we omit it.

Case III. $\chi(x+1)=1,\chi(x)=-1$. From (12), we have
$bu^{3}_{x}+b^{3}u_{x}=x+b^{4}-1$ in this case, and then we have

$(u_{x}+b)^{4}=-b^{4}-1$ (13)

by (11). If there are two distinct solutions in this case, namely $x_{3}$ and
$x^{\prime}_{3}$, then $u_{x_{3}}$ and $u_{x^{\prime}_{3}}$ satisfy (13) with
$\chi(x_{3}+1)=\chi(x^{\prime}_{3}+1)=1$ and
$\chi(x_{3})=\chi(x^{\prime}_{3})=-1$. Consequently
$(u_{x_{3}}+b)^{4}=(u_{x^{\prime}_{3}}+b)^{4}$ can be obtained from (13). Then
we have $u_{x_{3}}+b=-(u_{x^{\prime}_{3}}+b)$ since $x_{3}\neq
x^{\prime}_{3}$, which leads to
$u_{x_{3}}=b-u_{x^{\prime}_{3}}=u_{x^{\prime}_{3}+1}$. However, the above
conclusion contradicts to $\chi(u_{x_{3}})=\chi(x_{3})=-1$ and
$\chi(u_{x^{\prime}_{3}+1})=\chi(x^{\prime}_{3}+1)=1$. We conclude that Case
III has at most one solution.

Case IV. $\chi(x+1)=-1,\chi(x)=1$. In this case we have
$bu^{3}_{x}+b^{3}u_{x}=-x+b^{4}+1$ from (12), and then

$(u_{x}+b)^{4}=-b^{4}+1$ (14)

by (11). Similar to Case III, we can obtain that this case has at most one
solution.

Next we will prove for fixed $b$, (10) cannot have solutions in Case I and
Case II simultaneously. Otherwise, suppose that $x_{1}$ and $x_{2}$ are
solutions of (10) in Case I and Case II with $\chi(x_{1}+1)=\chi(x_{1})=1$ and
$\chi(x_{2}+1)=\chi(x_{2})=-1$ respectively. Then we have
$bu^{3}_{x_{1}}+b^{3}u_{x_{1}}=b^{4}-1$ and
$bu^{3}_{x_{2}}+b^{3}u_{x_{2}}=b^{4}+1$, where $u_{x_{1}}$ and $u_{x_{2}}$ we
defined before. Now we have
$b(u_{x_{1}}+u_{x_{2}})^{3}+b^{3}(u_{x_{1}}+u_{x_{2}})=-b^{4}$ and the
consequent $u_{x_{1}}+u_{x_{2}}=b$. From (10), we can obtain
$u_{x_{2}}=u_{x_{1}+1}$, which contradicts $\chi(u_{x_{2}})=\chi(x_{2})=-1$
and $\chi(u_{x_{1}+1})=\chi(x_{1}+1)=1$. Therefore, we conclude that (10) has
at most one solution in Cases I and II for fixed $b\in{\mathrm{GF}}(3^{n})$.

Then we prove for fixed $b$, (10) cannot have solutions in Case III and Case
IV simultaneously. Otherwise, suppose that $x_{3}$ and $x_{4}$ are solutions
of (10) in Case III and Case IV with $\chi(x_{3}+1)=1,\chi(x_{3})=-1$ and
$\chi(x_{4}+1)=-1,\chi(x_{4})=1$ respectively. Then $x_{3}$ and $x_{4}$
satisfy (13) and (14) respectively. By the sum of (13) and (14), we have
$(u_{x_{3}}+b)^{4}+(u_{x_{4}}+b)^{4}=b^{4}$, that is,

$(u^{2}_{x_{3}}-bu_{x_{3}}+u^{2}_{x_{4}}-bu_{x_{4}}+b^{2})^{2}=-u_{x_{3}}(b-u_{x_{3}})u_{x_{4}}(b-u_{x_{4}}).$
(15)

Note that $b-u_{x_{3}}=u_{x_{3}+1}$ and $b-u_{x_{4}}=u_{{x_{4}}+1}$, the
right-hand side of (15) is a nonzero nonsquare element, which is a
contradiction. We conclude that (10) has at most one solution in Cases III and
IV for fixed $b\in{\mathrm{GF}}(3^{n})$. From the above discussions, (10) has
at most two solutions in ${\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$.

One can easily calculate that $\Delta(0)=1$ and $\Delta(-1)=-1$. For $b=1$ and
$b=-1$, it can be verified that $\Delta(x)=1$ and $\Delta(x)=-1$ has no
solution in ${\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$, i,e,
$\delta(1)=\delta(-1)=1$. Then we obtain $\delta(b)\leq 2$ for any $b$, this
leads to ${}_{-1}\Delta_{F}\leq 2$ by Lemma 1 and $\gcd(d,3^{n}-1)=1$ .

For $n\equiv 3(\mathrm{mod}~{}4)$ and $d^{\prime}=d+\frac{3^{n}-1}{2}$, we
list the following theorems without proof.

###### Theorem 3.2

Let $F(x)=x^{d}$ be a power function over ${\mathrm{GF}}(3^{n})$, where
$n\equiv 3(\mathrm{mod}~{}4)$ and $d=\frac{3^{n+1}-1}{8}$. We have
${}_{-1}\Delta_{F}\leq 4$.

###### Corollary 2

Let $F^{\prime}(x)=x^{d^{\prime}}$ be a power function over
${\mathrm{GF}}(3^{n})$, where $n$ is an odd integer and
$d^{\prime}=\frac{3^{n+1}-1}{8}+\frac{3^{n}-1}{2}$. We have
${}_{-1}\Delta_{F^{\prime}}\leq 2$ when $n\equiv 3(\mathrm{mod}~{}4)$ and
${}_{-1}\Delta_{F^{\prime}}\leq 4$ when $n\equiv 1(\mathrm{mod}~{}4)$.

##  4 $-1$-differential uniformity of
$x^{\frac{3^{n}+1}{4}+\frac{3^{n}-1}{2}}$ over ${\mathrm{GF}}(3^{n})$

It was proved in HRS  that the power function $x^{d}$ is an APN function over
${\mathrm{GF}}(3^{n})$, where $n$ is an odd integer and
$d=\frac{3^{n}+1}{4}+\frac{3^{n}-1}{2}$. The $-1$-differential uniformity is
considered as follows.

###### Theorem 4.1

Let $F(x)=x^{d}$ be a power function over ${\mathrm{GF}}(3^{n})$, where $n$ is
odd and $d=\frac{3^{n}+1}{4}+\frac{3^{n}-1}{2}$. Then ${}_{-1}\Delta_{F}\leq
4$.

###### Proof

One can easily obtain that $d$ is even and $\gcd(d,3^{n}-1)=2$. Note that
$\chi(-1)=-1$ since $n$ is odd. We consider the $-1$-differential equation

$\Delta(x)=(x+1)^{d}+x^{d}=b.$ (16)

When $b=0$, (16) has no solution. For fixed $b\in{\mathrm{GF}}(3^{n})^{*}$,
let $x\in{\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$ is a solution of (16), we
distinguish the following four cases.

Case I. $\chi(x+1)=\chi(x)=1$. Let $x+1=\alpha^{2}$ and $x=\beta^{2}$ for
$\alpha,\beta\in{\mathrm{GF}}(3^{n})^{*}$, then $\alpha^{2}-\beta^{2}=1$. We
can obtain $\chi(\alpha)\alpha+\chi(\beta)\beta=b$ from (16). We have

$\beta^{2}+1=\alpha^{2}=(\chi(\alpha)\alpha)^{2}=(b-\chi(\beta)\beta)^{2}=b^{2}+b\chi(\beta)\beta+\beta^{2}.$

One can obtain $\chi(\beta)\beta=b^{-1}-b$ and
$x=\beta^{2}=(\chi(\beta)\beta)^{2}=(b^{-1}-b)^{2}$. This case has at most one
solution.

Case II. $\chi(x+1)=\chi(x)=-1$. Let $x+1=-\alpha^{2}$ and $x=-\beta^{2}$ for
$\alpha,\beta\in{\mathrm{GF}}(3^{n})^{*}$, then $\alpha^{2}-\beta^{2}=-1$.
Similar to Case I, we can obtain $x=-(b+b^{-1})^{2}$. This case has at most
one solution.

Case III. $\chi(x+1)=1,\chi(x)=-1$. Let $x+1=\alpha^{2}$ and $x=-\beta^{2}$
for $\alpha,\beta\in{\mathrm{GF}}(3^{n})^{*}$, then $\alpha^{2}+\beta^{2}=1$.
We can obtain $\chi(\alpha)\alpha+\chi(\beta)\beta=b$ from (16). Let
$\gamma=\chi(\beta)\beta$, which is a square element in
${\mathrm{GF}}(3^{n})$. Then $\gamma^{2}=\beta^{2}$ and $\gamma$ satisfies
$(b-\gamma)^{2}+\gamma^{2}=1$, i.e.

$\gamma^{2}-b\gamma+1-b^{2}=0,$ (17)

which is a quadratic equation on $\gamma$. Equation (17) has most two
solutions, then we can obtain at most two $x$’s since $x=-\gamma^{2}$. This
case has at most two solutions.

Case IV. $\chi(x+1)=-1,\chi(x)=1$. Let $x+1=-\alpha^{2}$ and $x=\beta^{2}$ for
$\alpha,\beta\in{\mathrm{GF}}(3^{n})^{*}$, then $\alpha^{2}+\beta^{2}=-1$. We
can obtain $\chi(\alpha)\alpha+\chi(\beta)\beta=b$ from (16). Let
$\gamma=\chi(\beta)\beta$, which is a square element in
${\mathrm{GF}}(3^{n})$. Then $\gamma^{2}=\beta^{2}$ and $\gamma$ satisfies
$(b-\gamma)^{2}+\gamma^{2}=-1$, i.e.

$\gamma^{2}-b\gamma-1-b^{2}=0,$ (18)

which is a quadratic equation on $\gamma$. Equation (18) has most two
solutions, then we can obtain at most two $x$’s since $x=\gamma^{2}$. This
case has at most two solutions.

Note that $x$ is a solution of (16) if and only if $-x-1$ is a solution of
(16). This implies that when $x\neq 1$ (the corresponds $b\neq-1$), if Case
III (the same for Case IV) has solutions, it must has two solutions. Next we
prove that for fixed $b\in{\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$, (16)
cannot have solution in Case III and Case IV simultaneously. Suppose on the
contrary that $x_{1}$, $x_{2}$ are distinct solutions of (16) for some given
$b$ in Case III, and $x_{3}$, $x_{4}$ are distinct solutions of (16) for the
same $b$ in Case IV. By the discussions above, each $x_{i},1\leq i\leq 4$
corresponds to square element $\gamma_{i}$. Moreover, $\gamma_{1}$,
$\gamma_{2}$ are the two solutions of (17), and $\gamma_{3}$, $\gamma_{4}$ are
the two solutions of (18). They satisfy
$\gamma_{1}+\gamma_{2}=\gamma_{3}+\gamma_{4}=b$,
$\gamma_{1}\gamma_{2}=1-b^{2}$ and $\gamma_{3}\gamma_{4}=-1-b^{2}$. We can
obtain
$\gamma^{2}_{1}+\gamma^{2}_{2}+\gamma^{2}_{3}+\gamma^{2}_{4}=(\gamma_{1}+\gamma_{2})^{2}+\gamma_{1}\gamma_{2}+(\gamma_{3}+\gamma_{4})^{2}+\gamma_{3}\gamma_{4}=0$.
Since $\gamma_{4}\neq 0$, let $\delta_{i}=\gamma_{i}/\gamma_{4}$, $1\leq i\leq
3$, then $\delta_{1},\delta_{2}$ and $\delta_{3}$ are square elements, and
they satisfy $\delta_{1}+\delta_{2}-\delta_{3}-1=0$ and
$\delta^{2}_{1}+\delta^{2}_{2}+\delta^{2}_{3}+1=0$. Replace by
$\delta_{3}=\delta_{1}+\delta_{2}-1$, we have the following quadratic equation
on $\delta_{1}$.

$\delta^{2}_{1}-(\delta_{2}-1)\delta_{1}+(\delta^{2}_{2}-\delta_{2}+1)=0.$

The discriminate of the above quadratic equation is
$\Delta=(\delta_{2}-1)^{2}-(\delta^{2}_{2}-\delta_{2}+1)=-\delta_{2}$, which
is a nonzero nonsquare element in ${\mathrm{GF}}(3^{n})$. It contradicts to
$\delta_{1}\in{\mathrm{GF}}(3^{n})$. Then we proved that for
$b\in{\mathrm{GF}}(3^{n})^{*}$, (16) has at most $4$ solutions in
${\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$.

One can easily check that $\Delta(0)=\Delta(-1)=1$. For $b=1$, it can be
verified that $\Delta(x)=1$ has no solution in the four cases, i.e.,
$\Delta(x)=1$ has no solution in ${\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$,
$\delta(1)=2$. For $b=-1$, it can be verified that $x=1$ is the only solution
of (16), i.e. $\delta(-1)=1$. This with the discussions above leads to
${}_{-1}\Delta_{F}\leq 4$.

##  5 $-1$-differential uniformity of
$x^{(3^{\frac{n+1}{4}}-1)(3^{\frac{n+1}{2}}+1)}$ over ${\mathrm{GF}}(3^{n})$

In ZW11 , the authors studied the power function $F(x)=x^{d}$ over
${\mathrm{GF}}(3^{n})$, where $n\equiv 3(\mathrm{mod}~{}4)$ and
$d=(3^{\frac{n+1}{4}}-1)(3^{\frac{n+1}{2}}+1)$. It was shown that $x^{d}$ is
an APN function. In what follows, we discuss the $-1$-differential uniformity
of $F(x)$.

###### Theorem 5.1

Let $F(x)=x^{d}$ be a power function over ${\mathrm{GF}}(3^{n})$, where
$n\equiv 3(\mathrm{mod}~{}4)$, $d=(3^{m}-1)(3^{2m}+1)$ and $m=\frac{n+1}{4}$.
Then ${}_{-1}\Delta_{F}\leq 4$.

###### Proof

Note that $d$ is an even number and $\gcd(d,3^{n}-1)=2$. For
$b\in{\mathrm{GF}}(3^{n})$, we consider equation

$\Delta(x)=(x+1)^{d}+x^{d}=b.$ (19)

It is easy to see that $\Delta(0)=\Delta(-1)=1$, and (19) has no solution when
$b=0$. Let $x\in{\mathrm{GF}}(3^{n})\setminus\\{0,-1\\}$ be a solution of (19)
for some given $b\in{\mathrm{GF}}(3^{n})^{*}$. Denote by $u_{x+1}=(x+1)^{d}$
and $u_{x}=x^{d}$. Since $\frac{3^{m}+1}{2}\cdot d=\frac{3^{n+1}-1}{2}\equiv
1+\frac{3^{n}-1}{2}(\mathrm{mod}~{}3^{n}-1)$, we have
${u_{x}}^{\frac{3^{m}+1}{2}}=\chi(x)x$ and
${u_{x+1}}^{\frac{3^{m}+1}{2}}=\chi(x+1)(x+1)$. One can easily see that if
$u_{x}$ and $\chi(x)$ are given, $x$ can be determined uniquely.

Let $\xi\in{\mathrm{GF}}(3^{2n})\setminus\\{0,\pm 1\\}$ such that
$\frac{u_{x}}{b}=\xi+\frac{1}{\xi}-1=\frac{(\xi+1)^{2}}{\xi}$, then we have
$\frac{u_{x+1}}{b}=-\xi-\frac{1}{\xi}-1=-\frac{(\xi-1)^{2}}{\xi}$ by (19).
Moreover, we can obtain
$\chi(x)x={u_{x}}^{\frac{3^{m}+1}{2}}=(\frac{b(\xi+1)^{2}}{\xi})^{\frac{3^{m}+1}{2}}$
and
$\frac{b(\xi+1)^{2}}{\xi}=x^{d}=(\frac{b(\xi+1)^{2}}{\xi})^{\frac{3^{m}+1}{2}\cdot
d}$. Similarly,
$-\frac{b(\xi-1)^{2}}{\xi}=(x+1)^{d}=(-\frac{b(\xi-1)^{2}}{\xi})^{\frac{3^{m}+1}{2}\cdot
d}$. Then $\xi$ satisfies
$-(\frac{\xi+1}{\xi-1})^{2}=(\frac{\xi+1}{\xi-1})^{(3^{m}+1)d}$, i.e.,
$(\frac{\xi+1}{\xi-1})^{3(3^{n}-1)}=-1$. This with
$\xi\in{\mathrm{GF}}(3^{2n})$ leads to $\xi^{3^{n}+1}=1$. In the following, we
discuss equation (19) in two cases.

Case 1. $\chi(x+1)=\chi(x)$.

In this case,
${u_{x+1}}^{\frac{3^{m}+1}{2}}-{u_{x}}^{\frac{3^{m}+1}{2}}=\chi(x+1)(x+1)-\chi(x)x=\chi(x)$.
That is,

$(-\frac{b(\xi-1)^{2}}{\xi})^{\frac{3^{m}+1}{2}}-(\frac{b(\xi+1)^{2}}{\xi})^{\frac{3^{m}+1}{2}}=\chi(x).$

We deduce the following equation

$(-1)^{\frac{3^{m}+1}{2}}(\xi-1)^{3^{m}+1}-(\xi+1)^{3^{m}+1}=\chi(x)b^{-\frac{3^{m}+1}{2}}\xi^{\frac{3^{m}+1}{2}}.$
(20)

Two subcases are considered as follows.

Subcase 1.1. $\frac{3^{m}+1}{2}$ is even, i.e., $m$ is odd. Then (20) becomes
$\xi^{3^{m}}+\xi=\chi(x)b^{-\frac{3^{m}+1}{2}}\xi^{\frac{3^{m}+1}{2}}$. Let
$t=\xi^{\frac{3^{m}-1}{2}}$, then
$t_{1,2}=-\chi(x)b^{-\frac{3^{m}+1}{2}}\pm\sqrt{b^{-(3^{m}+1)}-1}$. Since $m$
is odd, then $\gcd(m,2n)=1$ and $\gcd(\frac{3^{m}-1}{2},3^{2n}-1)=1$. We can
obtain a unique $\xi_{1}$ from $\xi^{\frac{3^{m}-1}{2}}=t_{1}$ since
$\gcd(\frac{3^{m}-1}{2},3^{2n}-1)=1$. For $t_{2}=t^{-1}_{1}$, we can also
obtain a unique $\xi_{2}$ such that $\xi_{2}^{\frac{3^{m}-1}{2}}=t_{2}$. Note
that $\xi_{2}=\xi^{-1}_{1}$ and they give the same $u_{x}$.

Subcase 1.2. $\frac{3^{m}+1}{2}$ is odd, i.e., $m$ is even. Then (20) becomes
$\xi^{3^{m}+1}+1=\chi(x)b^{-\frac{3^{m}+1}{2}}\xi^{\frac{3^{m}+1}{2}}$. Let
$t=\xi^{\frac{3^{m}+1}{2}}$, then
$t_{1,2}=-\chi(x)b^{-\frac{3^{m}+1}{2}}\pm\sqrt{b^{-(3^{m}+1)}-1}$. Since $m$
is even, then $\gcd(m,2n)=2$ and $\gcd(\frac{3^{m}+1}{2},3^{2n}-1)=1$. We can
obtain a unique $\xi_{1}$ from $\xi^{\frac{3^{m}+1}{2}}=t_{1}$ since
$\gcd(\frac{3^{m}+1}{2},3^{2n}-1)=1$. For $t_{2}=t^{-1}_{1}$, we can also
obtain a unique $\xi_{2}$ such that $\xi_{2}^{\frac{3^{m}+1}{2}}=t_{2}$. Note
that $\xi_{2}=\xi^{-1}_{1}$ and they give the same $u_{x}$.

By discussions in the above two subcases, we conclude that one can obtain a
unique $u_{x}$ from given $b$ and $\chi(x)$, and then we find at most one
solution of (20) for each $\chi(x)$. This case has at most $2$ solutions.

Case 2. $\chi(x+1)=-\chi(x)$.

In this case,
${u_{x+1}}^{\frac{3^{m}+1}{2}}+{u_{x}}^{\frac{3^{m}+1}{2}}=\chi(x+1)(x+1)+\chi(x)x=-\chi(x)$.
That is,

$(-\frac{b(\xi-1)^{2}}{\xi})^{\frac{3^{m}+1}{2}}+(\frac{b(\xi+1)^{2}}{\xi})^{\frac{3^{m}+1}{2}}=-\chi(x).$

We deduce the following equation

$(-1)^{\frac{3^{m}+1}{2}}(\xi-1)^{3^{m}+1}+(\xi+1)^{3^{m}+1}=-\chi(x)b^{-\frac{3^{m}+1}{2}}\xi^{\frac{3^{m}+1}{2}}.$
(21)

We have following two subcases.

Subcase 2.1. $\frac{3^{m}+1}{2}$ is even. Then (21) becomes

$\xi^{3^{m}+1}+1=\chi(x)b^{-\frac{3^{m}+1}{2}}\xi^{\frac{3^{m}+1}{2}}.$

Let $t=\xi^{\frac{3^{m}+1}{2}}$, if $\chi(x)=1$, then
$t_{1,2}=-b^{-\frac{3^{m}+1}{2}}\pm\sqrt{b^{-(3^{m}+1)}-1}$. Note that
$t_{2}=t^{-1}_{1}$ and they give the same $u_{x}$’s, we only consider $t_{1}$.
Since $\frac{3^{m}+1}{2}$ is even, $m$ is odd, then
$\gcd(\frac{3^{m}+1}{2},3^{n}+1)=2$. We can obtain two solutions, namely
$\pm\xi_{1}$, from $\xi^{\frac{3^{m}+1}{2}}=t_{1}$ since
$\gcd(\frac{3^{m}+1}{2},3^{n}+1)=2$. If $\chi(x)=-1$, then
$t_{3,4}=b^{-\frac{3^{m}+1}{2}}\pm\sqrt{b^{-(3^{m}+1)}-1}$. We only consider
$t_{4}$, which satisfies $t_{4}=-t_{1}$. Similarly, we obtain another two
$\xi$’s, namely $\delta\xi_{1}$, $-\delta\xi_{1}$, where
$\delta\in{\mathrm{GF}}(3^{2n})$ with $\delta^{2}=-1$. In this subcase, we get
four distinct $\xi$’s and each of them corresponds a possible solution of
(19).

Subcase 2.2. $\frac{3^{m}+1}{2}$ is odd. Then (21) becomes

$\xi^{3^{m}}+\xi=\chi(x)b^{-\frac{3^{m}+1}{2}}\xi^{\frac{3^{m}+1}{2}}.$

Let $t=\xi^{\frac{3^{m}-1}{2}}$, if $\chi(x)=1$, then
$t_{1,2}=-b^{-\frac{3^{m}+1}{2}}\pm\sqrt{b^{-(3^{m}+1)}-1}$. We only consider
the equation $\xi^{\frac{3^{m}-1}{2}}=t_{1}$ since the solutions of another
equation correspond the same $u_{x}$’s. Since $\frac{3^{m}+1}{2}$ is odd, $m$
is even, and $\gcd(\frac{3^{m}-1}{2},3^{n}+1)=4$. We obtain four solutions
from $\xi^{\frac{3^{m}-1}{2}}=t_{1}$, namely
$\xi_{2},\delta\xi_{2},-\xi_{2},-\delta\xi_{2}$, where
$\delta\in{\mathrm{GF}}(3^{2n})$ with $\delta^{2}=-1$. If $\chi(x)=-1$, then
$t_{3,4}=b^{-\frac{3^{m}+1}{2}}\pm\sqrt{b^{-(3^{m}+1)}-1}$. We only consider
$t_{4}$, which satisfies $t_{4}=-t_{1}$. If $\xi^{\prime}_{2}$ is a solution
of $\xi^{\frac{3^{m}-1}{2}}=t_{4}=-t_{1}$, then
$(\frac{\xi^{\prime}_{2}}{\xi_{2}})^{\frac{3^{m}-1}{2}}=-1$. We obtain that
$(\frac{\xi^{\prime}_{2}}{\xi_{2}})^{4}=1$ from $\gcd(3^{m}-1,3^{n}+1)=4$,
i.e., $\xi^{\prime}_{2}=\delta^{i}\xi_{2}$, $0\leq i\leq 3$. That means
$\xi^{\frac{3^{m}-1}{2}}=t_{4}$ cannot contribute new $\xi$’s. We also obtain
four distinct $\xi$’s in this subcase.

Recall that $u_{x}=b(\xi+\frac{1}{\xi}-1)$, in the following we prove that
$\xi$ and $\delta\xi$ cannot contribute solutions of (19) simultaneously,
where $\delta$ we defined before. More precisely, let
$u_{x_{1}}=b(\xi+\frac{1}{\xi}-1)$ and
$u_{x_{2}}=b(\delta\xi+\frac{1}{\delta\xi}-1)$, then we have

$(u_{x_{1}}+b)^{2}+(u_{x_{2}}+b)^{2}=b^{2}((\xi+\frac{1}{\xi})^{2}+(\delta\xi+\frac{1}{\delta\xi})^{2})=b^{2}.$

The above identity can be rewritten as

$(u_{x_{1}}+u_{x_{2}}+b)^{2}=-u_{x_{1}}u_{x_{2}},$

which is a contradiction. That means each of subcases 2.1 and 2.2 has at most
two solutions.

By discussions as above, we conclude that ${}_{-1}\Delta_{F}\leq 4$. The proof
is finished.

##  6 concluding remarks

In this paper, we studied the $-1$-differential uniformity of ternary APN
power functions. We obtain many classes of power functions with low
$-1$-differential uniformity, and some of them are almost perfect
$-1$-nonlinear. It is mentioned that in this paper we give the upper bound of
the $-1$-differential uniformity of some power functions, it is better to
study whether the equality holds. In this paper, we only studied $c=-1$, it is
also good to study the $c$-differential properties for $\pm 1\neq
c\in{\mathrm{GF}}(3^{n})$. Our future work is to find more power functions
with low $c$-differential uniformity. This topic is widely open. Power
functions with low usual differential uniformity are useful in sequences,
coding theory, and combinatorial designs. It is worth finding the applications
of power functions with low $c$-differential uniformity in such areas.

##  7 Acknowledgments

H. Yan’s research was supported by the National Natural Science Foundation of
China Grant (No.11801468) and the Guangxi Key Laboratory of Cryptography and
Information Security Grant (No. GCIS201814).

## References

  * (1) Beth, T., Ding, C.: On almost perfect nonlinear permutations, in Advances in Cryptography. EUROCRYPT 93 (Lecture Notes in Computer Science). New York: Springer-Verlag, vol. 765, pp. 65-76, 1994.
  * (2) Blondeau, C., Canteaut, A., Charpin, P.: Differential properties of power functions, Int. J. Inf. Coding Theory, 1(2), 149–170(2010)
  * (3) Borisov, N., Chew, M., Johnson, R., Wagner, D.: Multiplicative Differentials, In: Daemen J., Rijmen V. (eds) Fast Software Encryption. FSE 2002\. Lecture Notes in Computer Science, vol 2365. Springer, Berlin, Heidelberg, 2002.
  * (4) Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems, In Alfred Menezes and Scott A. Vanstone, editors, Advances in Cryptology-CRYPTO’ 90, 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings, volume 537 of Lecture Notes in Computer Science, pages 2-21. Springer, 1990.
  * (5) Biham, E., Shamir, A.: Differential Cryptanalysis of the Data Encryption Standard. Springer, 1993.
  * (6) Bartoli, D., Timpanella, M.: On a generalization of planar functions, J. Algebr. Comb, DOI:https://doi.org/10.1007/s10801-019-00899-2 (2019)
  * (7) Canteaut, A., Videau, M.: Degree of composition of highly nonlinear functions and applications to higher order differential cryptanalysis, in Advances in Cryptology – EUROCRYPT 2002, Springer, Berlin, 2002, vol. 2332, Lecture Notes in Comput. Sci., pp. 518–533.
  * (8) Coulter, R.S., Matthews, R.W.: Planar functions and planes of Lenz-Barlotti class II, Des. Codes Cryptogr. 10, 167-184 (1997)
  * (9) Courtois, N., Pieprzyk, J.: Cryptanalysis of block ciphers with overdefined systems of equations, in Advances in Cryptology – ASIACRYPT 2002, Springer, Berlin, 2002, vol. 2501, Lecture Notes in Comput. Sci., pp. 267–287.
  * (10) Dembowski, p., Ostrom, T. G.: Planes of order $n$ with collineation groups of order $n^{2}$, Math. Z. 193, 239-258(1968)
  * (11) Ding, C., Yuan, J.: A new family of skew Paley-Hadamard difference sets, J. Comb. Theory Ser. A 113, 1526-1535(2006)
  * (12) Dobbertin, H.: Almost perfect nonlinear power functions on ${\mathrm{GF}}(2^{n})$ : A new case for n divisible by 5, in Finite Fields and Applications, Augsburg, Germany, 1999, pp. 113-121.
  * (13) Dobbertin, H.: Almost perfect nonlinear power functions on ${\mathrm{GF}}(2^{n})$ : The Welch case, IEEE Trans. Inf. Theory 45(4), 1271-1275 (1999)
  * (14) Dobbertin, H.: Almost perfect nonlinear power functions on ${\mathrm{GF}}(2^{n})$ : The Niho case, Inform. Comput. 151(1-2), 57-72 (1999)
  * (15) Dobbertin, H., Mills, D., Muller, E. N., Pott, A., Willems, W.: APN functions in odd characteristic, Discr. Math. 267, 95-112 (2003)
  * (16) Ellingsen, P., Felke, P., Riera, C., St$\mathrm{\check{a}}$nic$\mathrm{\check{a}}$, P., Tkachenko, A.: C-differentials, multiplicative uniformity and (almost) perfect c-nonlinearity, IEEE Trans. Inform. Theory 66(9), 5781-5789 (2020)
  * (17) Gold, R.: Maximal recursive sequences with 3-valued recursive crosscorrelation function, IEEE Trans.Inf .Theory 14(1), 154-156 (1968)
  * (18) Helleseth, T., Rong, C., Sandberg, D.: New families of almost perfect nonlinear power mappings, IEEE Trans. Inform. Theory 45(2), 475–485 (1999)
  * (19) Helleseth, T., Sandberg, D.: Some power mappings with low differential uniformity, Appl. Algebra Engrg. Commun. Comput. 8, 363-37 (1997)
  * (20) Jakobsen, T., Knudsen, L. R.: The interpolation attack on block ciphers, in Fast Software Encryption – FSE 1997, Springer, Berlin, 1997, vol. 1267, Lecture Notes in Comput. Sci., pp. 28–40.
  * (21) Janwa, H., Wilson, R. M.: Hyperplane sections of Fermat varieties in P3 in char. 2 and some applications to cyclic codes, in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Lecture Notes in Computer Science). Berlin, Germany: Springer-Verlag, vol. 673, pp. 180-194, 1993.
  * (22) Kasami, T.: The weight enumerators for several classes of subcodes of the $2$nd order binary reed-muller codes, Inform. Contr. 18, 369-394 (1971)
  * (23) Leducq, E.: New families of APN functions in characteristic 3 or 5, In: Arithmetic, Geometry, Cryptography and Coding Theory, Contemporary Mathematics, vol. 574, pp. 115-123, AMS 2012.
  * (24) Nyberg, K.: Differentially uniform mappings for cryptography, in Advances in Cryptography. EUR OCRYPT93 (Lecture Notes in Computer Science). New York: Springer-Verlag, 1994, vol. 765, pp. 55-64.
  * (25) Nyberg, K., Knudsen, L.: Provable security against differential cryptanalysis, in Proc. Advances in Cryptology-CRYPTO 92, 1993, vol. 740, Lecture Notes in Computer Science, pp. 566-574.
  * (26) Yan, H., Mesnager, S., Zhou, Z.: Power functions over finite fields with low $c$-differential uniformity, arXiv:2003.13019v3.
  * (27) Zha, Z., Wang, X.: Power functions with low uniformity on odd characteristic finite fields, Sci. China Math. 53(8), 1931-1940 (2010)
  * (28) Zha, Z., Wang, X.: Almost perfect nonlinear power functions in odd characteristic, IEEE Trans. Inf. Theory 57(7), 4826-4832 (2011)


11institutetext: Dept. of Computer Science, University of Saskatchewan, Canada
11email<EMAIL_ADDRESS>
11email<EMAIL_ADDRESS>
# Sparseout: Controlling Sparsity in Deep Networks

Najeeb Khan  Ian Stavness

###### Abstract

Dropout is commonly used to help reduce overfitting in deep neural networks.
Sparsity is a potentially important property of neural networks, but is not
explicitly controlled by Dropout-based regularization. In this work, we
propose Sparseout a simple and efficient variant of Dropout that can be used
to control the sparsity of the activations in a neural network. We
theoretically prove that Sparseout is equivalent to an $L_{q}$ penalty on the
features of a generalized linear model and that Dropout is a special case of
Sparseout for neural networks. We empirically demonstrate that Sparseout is
computationally inexpensive and is able to control the desired level of
sparsity in the activations. We evaluated Sparseout on image classification
and language modelling tasks to see the effect of sparsity on these tasks. We
found that sparsity of the activations is favorable for language modelling
performance while image classification benefits from denser activations.
Sparseout provides a way to investigate sparsity in state-of-the-art deep
learning models. Source code for Sparseout could be found at
https://github.com/najeebkhan/sparseout.

##  1 Introduction

Sparsity is often thought to be a desirable property for artificial neural
networks. This is likely rooted in early neuroscience studies that discovered
sparse coding in the visual cortex [1] hypothesizing that at any given time,
only a small number of neurons are used to encode sensory information.
Sparsity has been observed both in connectivity [2] and representation [1]. To
mimic sparse coding from brain studies, researchers have devised approaches to
encourage sparsity when training ANNs.

Sparsity has been used to regularize models by imposing a _sparsity_
constraint on the activations of the neural network [3]. Many useful
properties are ascribed to sparsity in the literature. It has been
hypothesized that neurons that are rarely active are more interpretable than
those that are active most of the time [4]; images of natural world objects
can be described in terms of sparse statistically independent events; neural
networks with sparsity constraints learn filters that resemble the mammalian
visual cortex area V1 [1] and area V2 [5]; and sparsity allows faster learning
[6].

One of the main motivations behind sparsity based training methods is the
biological plausibility of these algorithms. However, recent studies have
questioned the pervasiveness of neural sparsity. The biological studies that
provide evidence for sparsity are performed when the subject is passive and in
reality sparsity might not be the mechanism that the brain uses in active
tasks [7]. Empirically for DNNs, new methods that may discourage sparsity,
such as Maxout [8] and DARC1 [9], have achieved better performance than sparse
methods in certain domains such as computer vision. Therefore it is not clear
whether or not sparsity is a generally desirable property for DNNs. We
hypothesize that sparsity will benefit some learning tasks and hinder others.
Therefore, new DNN training approaches that include the flexibility to either
encourage sparsity, where necessary, and discourage sparsity otherwise could
provide improved task performance.

There are many approaches for affecting the sparsity of a DNN during training
including the use of certain activation functions such as rectified linear
units [10]. One of the main ways is through regularization and several
deterministic regularization algorithms have been proposed to train deep
neural networks with sparse weights [11, 12, 13] and sparse activations [14,
15, 16, 10, 17].

Training deep neural networks with deterministic regularization and
backpropagation results in correlated activities of the neurons. To prevent
such co-adaptations as well as regularize the models, stochastic
regularization methods are used. Stochastic methods such as Dropout, Bridgeout
and Shakeout have been shown to be equivalent to ridge, bridge and elastic-net
penalties on the model weights. Previous stochastic regularization methods
that explicitly encourage sparsity, i.e., Shakeout and Bridgeout require a new
set of masked weights per training example in a mini-batch making them
computationally expensive. Therefore, these existing methods cannot be applied
to large fully connected architectures. Likewise, Shakeout and Bridgeout
cannot be easily applied to other convolutional architectures such as DenseNet
and Wide-ResNet that provide current state-of-the-art performance for image
classification, because they cannot be used with highly optimized black-box
implementations such as cuDNN [18].

In this paper, we propose Sparseout, a stochastic regularization method that
is capable of either encouraging or discouraging sparsity in deep neural
networks. It provides an $L_{q}$-norm penalty on the network’s activations and
therefore can vary activation sparsity by its $q$ parameter. The computational
cost of Sparseout is comparable to Dropout and it can be applied to existing
optimized CNN and LSTM blocks, making it applicable to state-of-the-art
architectures. We provide theoretical and empirical results demonstrating the
bridge-regularization capability of Sparseout. We use Sparseout to evaluate
whether or not sparsity is beneficial for two distinct learning tasks: image
classification and language modeling.

##  2 Related work

Due to the over-parameterization of deep neural networks, they suffer from
large generalization error, specifically, when the dataset size is relatively
small. This phenomenon is known as over-fitting. Generalization error is upper
bounded by the model complexity [19] thus overfitting could be reduced by
controlling the complexity of the model.

One way to control the complexity of a model is to impose constraints on the
parameters of the model such as the weights in the neural networks. Such model
regularization methods can be classified into deterministic and stochastic
methods. Deterministic methods either remove redundant weights [13] or
penalize large magnitude weights. Weight penalties are imposed by adding a
regularization term to the loss function consisting of a norm of the weight
matrix [20].

Stochastic methods randomly perturb the weights so as to achieve minimal co-
dependency between neurons [21, 22, 23] as well as regularizing the model at
the same time. Stochastic regularization has become the standard practice in
training deep learning models and have outperformed deterministic
regularization methods on many tasks. Stochastic regularization techniques
have a Bayesian model averaging interpretation as well as they posses an
equivalence to weight penalties for linear models. In terms of Bayesian
estimation, weight penalties are equivalent to imposing a prior distribution
on the model weights.

Beside the weight penalty interpretation, a reason for the effectiveness of
stochastic regularization methods could be the prevention of correlated
activations. It has been shown that high correlation between activations of
the neurons results in overfitting. DeCov [24], reduces overfitting by adding
a penalty term to the cost function consisting of the co-variances among the
activations of the neurons over a mini-batch.

Another approach to control model complexity, inspired by sparse coding [1],
is to impose a _sparsity_ constraint on the activations of the neural network
[3]. To encourage sparsity of the activations, an $L_{1}$ norm of the
activations is added to the cost function [5]. Another form of penalty is to
add the KL-divergence of the expected activations and a preset target sparsity
value $\rho$ [4]. Liao et al. have used a clustering approach to obtain sparse
representation by encouraging activations to form clusters [17].

Another related technique that normalizes activations in the network so as to
have zero mean and unit variance is Batchnorm [25]. Although, the primary
purpose of Batchnorm is accelerating training/optimization of the neural
network rather than regularization, Batchnorm has reduced the need for
stochastic regularization in certain domains. The above mentioned sparsity-
inducing methods are deterministic and thus may result in correlated
activations. In this paper we propose Sparseout that implicitly imposes an
$L_{q}$ penalty on the activations thus allowing us to choose the level of
sparsity in the activations as well as the stochasticity preventing correlated
neural activities. Sparseout is different than Bridgeout [23] in that it is
applied to activations rather than the weights. Therefore, Sparseout is orders
of magnitude faster and practical than Bridgeout. We believe that Sparseout is
the first theoretically-motivated technique that is capable of simultaneously
controlling sparsity in activations and reducing correlations between them,
besides being equivalent to Dropout for $q=2$.

##  3 Sparseout

Consider a feedforward neural network layer $l$, the output of $l$-th is given
by

$\boldsymbol{a}^{l}=\sigma\big{(}\boldsymbol{W}^{l}\boldsymbol{a}^{l-1}+\boldsymbol{b}^{l}\big{)},$
(1)

where $\boldsymbol{W}^{l}$ and $\boldsymbol{b}^{l}$ are the weight matrix and
bias vector for the $l$-th layer, $\sigma$ is a non-linear activation function
and $\boldsymbol{a}^{l-1}$ is the output of the previous layer.

The Sparseout perturbed output of the $l$-th layer
$\boldsymbol{\widetilde{a}}^{l}$ is given by

$\boldsymbol{\widetilde{a}}_{i}^{l}=\begin{cases}\boldsymbol{a}_{i}^{l}-|\boldsymbol{a}_{i}^{l}|^{q/2}&\boldsymbol{r}_{i}=0\\\
\boldsymbol{a}_{i}^{l}+|\boldsymbol{a}_{i}^{l}|^{q/2}\big{(}\frac{1-p}{p}\big{)}&\boldsymbol{r}_{i}=\frac{1}{p}\\\
\end{cases}$ (2)

where $\boldsymbol{r}$ is a random mask vector randomly sampled from a
Bernoulli distribution with probability $p$ and scaled by $1/p$ and $q$
specifies the normed space to which the activations are restricted. Since the
random mask is scaled by $1/p$ during training, no changes to the neural
network are needed during testing. Since the training of the neural networks
is performed using the back-propagated gradients of the error, the gradient of
the Sparseout perturbed output is given by

$\frac{\partial\boldsymbol{\widetilde{a}}_{i}^{l}}{\partial\boldsymbol{a}_{i}^{l}}=1+\frac{q}{2}|\boldsymbol{a}_{i}^{l}|^{\frac{q}{2}-1}\big{(}\boldsymbol{r}_{i}-1\big{)}\operatorname{sgn}\big{(}\boldsymbol{a}_{i}^{l}\big{)},$
(3)

where $\operatorname{sgn}$ is the sign function.

Since Sparseout operates on the activations of the neural networks similar to
Dropout, Sparseout can be implemented with minimal changes to the existing
Dropout implementation. Sparseout can be used with the highly optimized black-
box implementations such as cuDNN [18]. The above Sparseout formulation is
applicable to any feedforward network layer such as convolutional or fully
connected layers as well as layers in recurrent neural networks.

###### Theorem 3.1

Sparseout is equivalent to an $L_{q}$ penalty on the features of a generalized
linear model.

For a generalized linear model with parameters $\boldsymbol{\beta}$, log
partition function $A$ and the perturbed design matrix
$\boldsymbol{\widetilde{X}}$ of dimension $n\times d$, the negative log
likelihood function could be split into a mean squared error term and a
penalty term [26, eq. 6] given by

$R(\boldsymbol{\beta})\approx\sum_{i=1}^{n}\frac{A^{\prime\prime}(\boldsymbol{X}_{i}\cdot\boldsymbol{\beta})}{2}Var[\widetilde{\boldsymbol{X}}_{i}\cdot\boldsymbol{\beta}]$
(4)

For the Sparseout perturbation
$\boldsymbol{\widetilde{X}}_{i,j}=\boldsymbol{X}_{i,j}[1+|\boldsymbol{X}_{i,j}|^{\frac{q-2}{2}}(\boldsymbol{r}_{j}-1)]$,
the variance of $\widetilde{\boldsymbol{X}}_{i}\cdot\boldsymbol{\beta}$ is
given by

$Var[\widetilde{\boldsymbol{X}}_{i}\cdot\boldsymbol{\beta}]=\sum_{j=1}^{d}\frac{1-p}{p}|\boldsymbol{X}_{i,j}|^{q}\beta_{j}^{2}$
(5)

Substituting in Equation 4 we have

$\displaystyle\hat{R}(\boldsymbol{\beta})$
$\displaystyle=\frac{1-p}{2p}||\Gamma\boldsymbol{X}||_{q}^{q},$ (6)

where
$\Gamma=[\boldsymbol{\beta}^{T}V(\boldsymbol{\beta})\boldsymbol{\beta}]^{\frac{2}{q}}$
and $V(\boldsymbol{\beta})=Diag(A)$. $\blacksquare$

###### Theorem 3.2

For non-negative activation functions, Dropout is equivalent to Sparseout when
$q=2$.

Setting $q=2$ in Equation 2 and considering the fact that $\boldsymbol{a}$ is
non-negative, we have
$\boldsymbol{\widetilde{a}}_{i}^{l}=\boldsymbol{r}_{i}\boldsymbol{a}_{i}^{l}$,
which is identical to the Dropout perturbation [21]. $\blacksquare$

$L_{q}$-normed spaces with different values of $L_{q}$ exhibit different
sparsity charactersitics. For $q<2$ the norm space is sparse while for $q>2$
the norm space is dense [27]. With Sparseout we can select the norm space of
the activations by choosing the value of the hyper-parameter $q$. Thus,
Sparseout allows us to control the level of sparsity in the activations of the
neural networks.

##  4 Experimental results

###  4.1 Sparsity characterization

To verify that Sparseout is capable of controlling sparsity of a neural
network’s activations, we train an autoencoder with a hidden layer of $512$
rectified linear units on the MNIST dataset. Dropout and Sparseout are applied
to the hidden layer activations with $p=0.5$ and different values of $q$ for
Sparseout. We measure sparsity of the hidden layer activations during testing
(when no perturbations are applied to the activations). To measure sparsity we
use the Hoyer’s measure $H$ [28]:

$H(\mathbf{x})=\frac{\sqrt{d}-\frac{|\mathbf{x}|_{1}}{|\mathbf{x}|_{2}}}{\sqrt{d}-1}$
(7)

where $\mathbf{x}$ is a $d$-dimensional vector, $|\mathbf{x}|_{1}$ is the
$L_{1}$-norm and $|\mathbf{x}|_{2}$ is the $L_{2}$-norm of $\mathbf{x}$. A
vector consisting of equal non-zero values has $H=0$ while vectors only having
one non-zero element has $H=1$. Figure 1 shows the Hoyer’s sparsity measure on
the test set as the training progresses for different values of $q$. As the
value of $q$ decreases below $2$, we see an increase in the sparsity of the
activations, whereas for $q$ values greater than $2$ the sparsity is reduced.
For $q=2$, Sparseout results in the same sparsity as Dropout. These results
confirm our theoretical analysis that Sparseout can be used to control
sparsity of the activations in the neural networks.

Figure 1: Average Hoyer’s sparsity measure of the hidden layer activations
calculated over the MNIST test set for an autoencoder trained on MNIST with
Dropout versus Sparseout with different values of $q$.

###  4.2 Computational cost

Sparseout is computationally efficient and incurs similar training cost as
Dropout. We train an autoencoder with two hidden layer sizes on MNIST with a
batch size of $128$ both on Nvidia GTX 1080 GPU. As shown in Table 1,
Sparseout is only fractionally more expansive than Dropout while Bridgeout is
an order of magnitude more expensive even for this simple model. Also doubling
the hidden layer size results in a doubling of the execution time for
Brigdeout while Sparseout and Dropout have almost constant execution time due
to utilization of GPU parallelism.

Table 1: Average execution time in seconds per epoch for different types of stochastic regularization for an autoencoder with different hidden layer sizes. Hidden layer size | Backprop | Dropout | Sparseout | Bridgeout
---|---|---|---|---
1024 | 5.2 | 5.3 | 5.8 | 31.6
2048 | 5.6 | 5.6 | 6.0 | 57.2

###  4.3 Image classification

Image classification is one of the key areas where deep neural networks have
been highly successful achieving state-of-the-art results. The CIFAR datasets
[29] are a standard benchmark for image classification. The CIFAR-$10$ dataset
consists of color images of size $32\times 32$ each belonging to one of the
ten classes of objects. The dataset is divided into a training set of $50000$
images and a test set of $10000$ images. The CIFAR-$100$ dataset is similar to
CIFAR-$10$ except that the images are divided into $100$ classes of objects,
thus making the classification task more harder than CIFAR-$10$. We used the
standard pre-processing of mean and standard deviation normalization. Random
cropping and random horizontal flips were used for data augmentation.

We use the wide residual network (WRN) architecture to evaluate the effect of
sparsity on classification accuracy using Sparseout. WRNs achieved state-of-
the-art accuracy on several image classification tasks including CIFAR-$10$
and CIFAR-$100$. WRNs are based on deep residual networks [30] that use
identity links between the input and output of each layer known as the
residual connections, but they employ fewer and wider layers. The residual
connections helps in training very deep neural networks consisting of upto a
thousand layers.

We employ a WRN with the basic building block shown in Figure 2. The
stochastic regularization is applied between the convolutional layers. Each
convolutional layer is preceded by batch normalization and rectified linear
unit activation function. In our experiments we use the WRN architecture
WRN-28-10 with depth 28 and a widening factor of 10. A Dropout probability of
$p=0.3$ was used. Stochastic gradient descent with a mini-batch of 64 was used
to train the networks. The learning rate was annealed from $0.1$ at $60$,
$120$ and $160$ epochs by a factor of $0.2$ as in the original WRN paper [31].

Figure 2: The basic building block of wide residual network architecture with
either Dropout or Sparseout stochastic regularization. Figure adapted from
[31]

####  4.3.1 Image Classification Results

For image classification we found that Sparseout with $q>2$ resulted in better
performance compared to values of $q<2$ as shown in Figure 3. For $q<2$ the
accuracy drops as the training progresses beyond around $100$ epochs
indicating overfitting. As shown in Table 2, error rate for $q=2.5$ is about
$1$ percent lower than Dropout for CIFAR-10 and $2.5$ percent lower for
CIFAR-100. Our baseline results are comparable to the baselines reported in
the literature for CIFAR-100 and better for CIFAR-10 [31, 32].

(a) CIFAR-10

(b) CIFAR-100

Figure 3: Test accuracy during training of WRN on CIFAR-10 and CIFAR-100 for Dropout versus Sparseout with different values of $q$. Table 2: Mean test errors for the same WRN network trained with Dropout and Sparseout with different values of $q$. Lower sparsity (high $q$) results in lower test error. Model | $p$ | $q$ | CIFAR10 | CIFAR100
---|---|---|---|---
WRN-28-10-Sparseout | 0.3 | 1.5 | 7.58 | 25.87
WRN-28-10-Sparseout | 0.3 | 1.85 | 5.92 | 24.65
WRN-28-10-Sparseout | 0.3 | 2.0 | 4.72 | 21.91
WRN-28-10-Dropout | 0.3 | - | 4.59 | 21.66
WRN-28-10-Sparseout | 0.3 | 2.5 | 3.63 | 19.07
WRN-28-10-Dropout [31] |  $p=$0.3 | 3.89 | 18.85
WRN-28-10-$L_{0_{hc}}$ [32] | - | 3.83 | 18.75

###  4.4 Language Modelling

Another task for which deep learning has been widely used is natural language
processing (NLP). The dimensionalty of NLP tasks is very high and sparse;
therefore, sparsity is likely to play an important role in such tasks.
Language modelling (LM) assigns a probability to a sequence of words. LM is an
important component of several NLP tasks such as speech recognition,
information retrieval and machine translation among others. Since LM is a
sequential task recurrent neural networks are used for it. Vanilla RNN are
difficult to train due to vanishing and exploding gradients problem. To
overcome these limitations, long short term memory (LSTM) models are used
instead [33].

The LSTM model is a type of recurrent neural network with layers consisting of
memory cells. The weights of the nodes in a memory cell learn the long term
information while a node with a self-connected edge retains short term
information. The input gate, forgetting gate and output gate help in
controling the flow of information in the LSTM. For a detailed review of the
LSTM formulation see Lipton et al. [34].

We adapt the baseline LSTM architecture for word level language modelling from
Merity et al. [35]. The model consists of 3 layers of 1150 units. To train the
baseline model we used the same hyper-parameters used by Merity et al.
111https://github.com/salesforce/awd-lstm-lm except that we used only
stochastic gradient descent for training.

We replace variants of Dropout with variants of Sparseout in the LSTM model.
Variational Dropout [36] is replaced with variational Sparseout where a single
random mask is used within a forward and backward pass. Embedding Dropout
applied to the word embedding layer is similarly replaced with embedding
Sparseout.

We evaluate the model on two standard word-level language modelling datasets
where the task is to predict the next word and the performance is evaluated on
perplexity which is the negative log likelihood raised to the exponent. The
first dataset is the Penn Treebank dataset [37] that contains $1$ million
words and a vocabulary size of $10,000$. The second dataset is the WikiText-2
dataset [38] which contains over $100$ million words and a vocabulary of size
$30,000$.

####  4.4.1 Language modeling results

Applying Sparseout with $q>2$ resulted in significant overfitting as shown in
Figure 4. For $q<2$ we found that Sparseout resulted in better prediction
performance than Dropout. For PTB dataset Sparseout results in $2.5$ percent
reduction in relative perplexity. For Wiki-2 dataset the reduction in relative
perplexity is $1.25$ percent as shown in Table 3.

(a) PTB

(b) Wiki-2

Figure 4: Validation perplexity for language modeling on PTB and Wiki-2 datasets for LSTM models trained with Dropout, Sparseout with $q=2.25$ to reduce sparsity, and Sparseout with $q=1.75$ to increase sparsity. Table 3: Single model test perplexities on PTB and Wiki-2 datasets for LSTM models trained with Dropout, Sparseout with $q=2.25$ to reduce sparsity, and Sparseout with $q=1.75$ to increase sparsity. Higher sparsity results in lower (better) relative perplexity. Model | Penn Tree Bank | WikiText-2
---|---|---
LSTM-Sparseout ($q=2.25$) | 62.7 | 70.18
LSTM-Dropout | 62.13 | 68.34
LSTM-Sparseout ($q=1.75$) | 60.57 | 67.17
AWD-LSTM-Dropout [35] | 57.3 | 65.8

##  5 Discussion

Existing literature is contradictory on whether sparsity is a good [14, 15,
16, 10, 17, 32] or bad [7, 39, 9, 8, 40] property for deep neural networks. No
previous study has evaluated sparse vs. non-sparse networks in a controlled
fashion with stochastic regularization. In this study, we propose a new
bridge-regularization scheme, Sparseout, which has the flexibility to control
sparsity and the efficiency to be applied to large networks.

We evaluated Sparseout with two distinct network architectures and machine
learning tasks: CNNs for image classification and LSTMs for language modeling.
Our empirical results show that lower sparsity improves image classification
performance, whereas higher sparsity improves performance on language
modeling. These results align with the fundamental differences between data
types: relatively tiny densely-featured images vs. sparsely-featured high-
dimensional language data.

In this study, we chose the most suitable architecture for each task: CNNs for
IID image classification and RNNs for sequential language modelling.
Therefore, we evaluated task-architecture in a coupled manner. For each task,
image classification or language modelling, we tested two datasets
(CIFAR10/CIFAR100 or PTB/WikiText-2) and obtained consistent results regarding
the benefit or lack thereof of sparse activations. It is possible, however,
that the inherent sparse nature of convolutional layers requires spreading of
the activations over all the neurons while enforced parsimony of
representation is helpful for the fully connected gates in an LSTM. Therefore,
decoupling the effect of data type from that of architecture is an important
consideration we plan to investigate as future work.

## Acknowledgments

This work was supported by the Natural Sciences and Engineering Research
Council of Canada (NSERC).

## References

  * [1] Olshausen, B.A., Field, D.J.:  Sparse coding with an overcomplete basis set: A strategy employed by V1?  Vision research 37(23) (1997) 3311–3325
  * [2] Morris, G., Nevet, A., Bergman, H.:  Anatomical funneling, sparse connectivity and redundancy reduction in the neural networks of the basal ganglia.  Journal of Physiology-Paris 97(4) (2003) 581–589
  * [3] Thom, M., Palm, G.:  Sparse activity and sparse connectivity in supervised learning.  Journal of Machine Learning Research 14(Apr) (2013) 1091–1143
  * [4] Hinton, G.:  A practical guide to training restricted Boltzmann machines.  Momentum 9(1) (2010) 926
  * [5] Lee, H., Ekanadham, C., Ng, A.Y.:  Sparse deep belief net model for visual area V2.  In: Advances in neural information processing systems. (2008) 873–880
  * [6] Schweighofer, N., Doya, K., Lay, F.:  Unsupervised learning of granule cell sparse codes enhances cerebellar adaptive control.  Neuroscience 103(1) (2001) 35–50
  * [7] Spanne, A., Jörntell, H.:  Questioning the role of sparse coding in the brain.  Trends in neurosciences 38(7) (2015) 417–427
  * [8] Goodfellow, I., Warde-farley, D., Mirza, M., Courville, A., Bengio, Y.:  Maxout networks.  In: Proceedings of the 30th International Conference on Machine Learning (ICML-13). (2013) 1319–1327
  * [9] Kawaguchi, K., Kaelbling, L.P., Bengio, Y.:  Generalization in deep learning.  arXiv preprint arXiv:1710.05468 (2017)
  * [10] Glorot, X., Bordes, A., Bengio, Y.:  Deep sparse rectifier neural networks.  In: Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. (2011) 315–323
  * [11] Hanson, S.J., Pratt, L.Y.:  Comparing biases for minimal network construction with back-propagation.  In: Advances in neural information processing systems. (1989) 177–185
  * [12] LeCun, Y., Denker, J.S., Solla, S.A., Howard, R.E., Jackel, L.D.:  Optimal brain damage.  In: NIPS. Volume 2. (1989) 598–605
  * [13] Han, S., Pool, J., Tran, J., Dally, W.:  Learning both weights and connections for efficient neural network.  In: Advances in Neural Information Processing Systems. (2015) 1135–1143
  * [14] Chauvin, Y.:  A back-propagation algorithm with optimal use of hidden units.  In: Advances in neural information processing systems. (1989) 519–526
  * [15] Mrázová, I., Wang, D.:  Improved generalization of neural classifiers with enforced internal representation.  Neurocomputing 70(16) (2007) 2940–2952
  * [16] Wan, W., Mabu, S., Shimada, K., Hirasawa, K., Hu, J.:  Enhancing the generalization ability of neural networks through controlling the hidden layers.  Applied Soft Computing 9(1) (2009) 404–414
  * [17] Liao, R., Schwing, A., Zemel, R., Urtasun, R.:  Learning deep parsimonious representations.  In: Advances in Neural Information Processing Systems. (2016) 5076–5084
  * [18] Chetlur, S., Woolley, C., Vandermersch, P., Cohen, J., Tran, J., Catanzaro, B., Shelhamer, E.:  cudnn: Efficient primitives for deep learning.  arXiv preprint arXiv:1410.0759 (2014)
  * [19] Shalev-Shwartz, S., Ben-David, S.:  Understanding machine learning: From theory to algorithms.  Cambridge university press (2014)
  * [20] Neyshabur, B., Tomioka, R., Srebro, N.:  Norm-based capacity control in neural networks.  In: Conference on Learning Theory. (2015) 1376–1401
  * [21] Srivastava, N., Hinton, G.E., Krizhevsky, A., Sutskever, I., Salakhutdinov, R.:  Dropout: a simple way to prevent neural networks from overfitting.  Journal of Machine Learning Research 15(1) (2014) 1929–1958
  * [22] Kang, G., Li, J., Tao, D.:  Shakeout: A new regularized deep neural network training scheme.  In: Thirtieth AAAI Conference on Artificial Intelligence. (2016)
  * [23] Khan, N., Shah, J., Stavness, I.:  Bridgeout: stochastic bridge regularization for deep neural networks.  arXiv preprint arXiv:1804.08042 (2018)
  * [24] Cogswell, M., Ahmed, F., Girshick, R., Zitnick, L., Batra, D.:  Reducing overfitting in deep networks by decorrelating representations.  arXiv preprint arXiv:1511.06068 (2015)
  * [25] Ioffe, S., Szegedy, C.:  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In: International Conference on Machine Learning. (2015) 448–456
  * [26] Wager, S., Wang, S., Liang, P.S.:  Dropout training as adaptive regularization.  In: Advances in neural information processing systems. (2013) 351–359
  * [27] Park, C., Yoon, Y.J.:  Bridge regression: adaptivity and group selection.  Journal of Statistical Planning and Inference 141(11) (2011) 3506–3519
  * [28] Hoyer, P.O.:  Non-negative matrix factorization with sparseness constraints.  Journal of machine learning research 5(Nov) (2004) 1457–1469
  * [29] Krizhevsky, A., Hinton, G.:  Learning multiple layers of features from tiny images.  Technical report, Citeseer (2009)
  * [30] He, K., Zhang, X., Ren, S., Sun, J.:  Deep residual learning for image recognition.  In: Proceedings of the IEEE conference on computer vision and pattern recognition. (2016) 770–778
  * [31] Zagoruyko, S., Komodakis, N.:  Wide residual networks.  arXiv preprint arXiv:1605.07146 (2016)
  * [32] Louizos, C., Welling, M., Kingma, D.P.:  Learning sparse neural networks through $l_{0}$ regularization.  In: International Conference on Learning Representations. (2018)
  * [33] Sundermeyer, M., Schlüter, R., Ney, H.:  Lstm neural networks for language modeling.  In: Thirteenth Annual Conference of the International Speech Communication Association. (2012)
  * [34] Lipton, Z.C., Berkowitz, J., Elkan, C.:  A critical review of recurrent neural networks for sequence learning.  arXiv preprint arXiv:1506.00019 (2015)
  * [35] Merity, S., Keskar, N.S., Socher, R.:  Regularizing and optimizing lstm language models.  arXiv preprint arXiv:1708.02182 (2017)
  * [36] Gal, Y., Ghahramani, Z.:  Dropout as a bayesian approximation: Insights and applications.  In: Deep Learning Workshop, ICML. (2015)
  * [37] Marcus, M.P., Marcinkiewicz, M.A., Santorini, B.:  Building a large annotated corpus of english: The penn treebank.  Comput. Linguist. 19(2) (June 1993) 313–330
  * [38] Merity, S., Xiong, C., Bradbury, J., Socher, R.:  Pointer sentinel mixture models.  arXiv preprint arXiv:1609.07843 (2016)
  * [39] Rigamonti, R., Brown, M.A., Lepetit, V.:  Are sparse representations really relevant for image classification?  In: Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, IEEE (2011) 1545–1552
  * [40] Gulcehre, C., Cho, K., Pascanu, R., Bengio, Y.:  Learned-norm pooling for deep feedforward and recurrent neural networks.  In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springer (2014) 530–546