TITLE: Is a groupoid determined by its Hopfish algebra?
QUESTION [9 upvotes]: This is a follow up to my question What is the precise relationship between groupoid language and noncommutative algebra language?.  I will briefly review some definitions; for details, a good place to look is Christian Blohmann, Alan Weinstein. Group-like objects in Poisson geometry and algebra. 2007. arXiv:math/0701499v1.  And actually, there are two versions of my question, one for groupoids and the other for categories.  So that I can avoid all analysis, I will restrict my attention to finite things; if you know the answer in, say, topological spaces, or smooth manifolds, or..., then I'm also interested.
A category is a span of sets $C = \{ C_0 \overset l \leftarrow C_1 \overset r \rightarrow C_0\}$ which is an algebra object in the category of $C_0,C_0$ spans.  I.e. there are maps of spans $i: \{C_0 = C_0 = C_0\} \to C$ and $m: C \underset{C_0}\times C \to C$ making the usual diagrams commute.  A category is a groupoid if additionally there is an involution ${^{-1}} : \{ C_0 \overset l \leftarrow C_1 \overset r \rightarrow C_0\} \to \{ C_0 \overset r \leftarrow C_1 \overset l \rightarrow C_0\}$ satisfying some condition.  A category $C$ is finite if both $C_0$ and $C_1$ are finite.
A finite-dimensional algebra $A$ (over a fixed field $\mathbb K$) is sesqui if it is equipped with a bimodule ${_A \Delta _{A\otimes A}}$ and an "associativity isomorphism" $$\varphi: {_A \Delta _{A\otimes A}} \underset{A\otimes A}\otimes \bigl( {_A A _A} \underset{\mathbb K}\otimes {_A \Delta _{A\otimes A}}\bigr) \overset\sim\to {_A \Delta _{A\otimes A}} \underset{A\otimes A}\otimes \bigl( {_A \Delta _{A\otimes A}}  \underset{\mathbb K}\otimes {_A A _A} \bigr) $$
of $A, A^{\otimes 3}$ bimodules, which satisfies a pentagon.  There should also be a "counit" bimodule $_A \epsilon _{\mathbb K}$, some triangle isomorphisms, and some more equations.
  A sesquialgebra is hopfish if a hard-to-write-down condition is satisfied; see Xiang Tang, Alan Weinstein, Chenchang Zhu. Hopfish algebras. 2006.  arXiv:math/0510421v2.  Let ${_A {\Delta^{\rm flip}} _{A\otimes A}}$ denote the bimodule $\Delta$ with the two right $A$-actions flipped.  A sesquialgebra is symmetric if it comes equipped with a bimodule isomorphism $\psi: {_A \Delta _{A\otimes A}} \overset\sim\to {_A {\Delta^{\rm flip}} _{A\otimes A}}$ so that $\varphi,\psi$ satisfy two hexagons.  A sesquialgebra is finite if $A,\Delta, \dots$ are finite-dimensional over $\mathbb K$.
Let $C = \{ C_0 \overset l \leftarrow C_1 \overset r \rightarrow C_0\}$ be a finite category.  Then it gives rise to a finite symmetric sesquialgebra as follows.  The algebra $A$ is given by the vector space $\mathbb K C_1$ with the convolution product (given on the basis by $a\otimes b \mapsto ab$ if $(a,b)$ is a composable pair of morphisms, and $a\otimes b \mapsto 0$ otherwise).  The bimodule $\Delta$ is given as the vector space with basis all pairs $(a,b) \in C_1 \times C_1$ with $l(a) = l(b)$.  I will let you work out the rest: the actions, the associator $\varphi$ and symmetrizer $\psi$, etc.  If $C$ is actually a groupoid, then $\mathbb K C_1$ is hopfish.
This construction extends to a 2-functor, and so sends equivalences of categories to Morita equivalences of sesquialgebras.

Question: It is well known that a groupoid $C$ cannot be recovered from the algebra $\mathbb K C_1$; compare for example the group with two elements, thought of as a groupoid with one object, and the set with two elements, thought of as a groupoid with only identity morphisms.  But the examples I know can be distinguished by remembering the hopfish structure.

Can a finite category be recovered from its symmetric sesquialgebra?
If not, can a finite groupoid be recovered from its symmetric hopfish structure?
Can an equivalence class of finite categories be recovered from the Morita-equivalence class of finite symmetric sesquialgebras?
If not, do we at least have the corresponding statement for groupoids/hopfish algebras?

In a footnote, Blohmann and Weinstein suggest that they do not know the answers to the above questions.  But that was three years ago; perhaps there has been more recent work?

REPLY [0 votes]: Let $A=KC_0$ be the direct sum of fields indexed by the base of the groupoid. Then the algebra $H=KC_1$ is an $A|K$-Hopf algebra in terminilogy going back to Sweedler. The groupoid can be recovered from it as the set of grouplike elements, in the same way as a group can be recovered from its Hopf group algebra.


TITLE: How to do continuous-time Bayesian updating?
QUESTION [6 upvotes]: I am reading a game theory lecture notes. Some parts involve a continuous time Bayesian updating computation which I didn't really understand.
There are two states $\{Good,Bad\}$. At time t people has prior belief that the state of world being $Good$ as $p_t$. There is conclusive signal which can confirm that the state is good. Within time interval $[t,t+d_t)$, the probability of good signal's arrival is $\lambda\cdot K_t$. Then it wrote the updating rule as
$$p_t+dp_t=\frac{p_t(1-\lambda\cdot K_td_t)}{1-p_t\lambda\cdot K_t d_t},$$
and further conclude that
$$\frac{dp_t}{d_t}=-\lambda p_t(1-p_t)K_t.$$
I didn't understand both computation here.
For the first result, it seems the author only record
$$p_{t+dt}(good|no\ news\ arrived).$$
Also, even if I accept the first equation, should I subtract $p_t$ on both sides and divided both sides by $d_t$? This does not give the result the author gave.

REPLY [5 votes]: Define $G$ and $B$ to be event of being in good and bad state, respectively. Let $I$ be event that no news arrives in the interval $[t, t+dt)$. As you state, we are interested in $\Pr(G|I)$, because if news arrives, then we are sure to be in good state. So, we are interested in evolution of our belief of being in good state as time passes without the arrival of news. Using Baye's theorem
$$
\begin{split}
\Pr(G|I)
&=
\frac{\Pr(I|G)\Pr(G)}{\Pr(I|G)\Pr(G)+\Pr(I|B)\Pr(B)}
=
\frac{(1-\lambda K_tdt)p_t}{(1-\lambda K_tdt)p_t + 1(1-p_t)}
\\
&=
\frac{(1-\lambda K_tdt)p_t}{1-\lambda p_tK_t dt}.
\end{split}
$$
The posterior probability after observing the information over time $[t, t+dt)$, be denoted by $p_t + dp_t$. Therefore,
$$
p_t + dp_t
=
\frac{(1-\lambda K_tdt)p_t}{1-\lambda p_tK_t dt}
$$
Simplifying it after ignoring $dp_tdt$, we get
$$
\frac{dp_t}{dt}
=
-\lambda p_t(1-p_t)K_t.
$$


TITLE: Why is the scaling factor in the Robertson-Walker metric squared?
QUESTION [0 upvotes]: Not much to add beyond the title. The Robertson-Walker metric solution to the field equations has the form
$$g_{\mu\nu}dx^\mu dx^\nu=-dt^2+a^2(t)\biggl(\frac{dr^2}{1-Kr^2}+r^2(d\theta^2+sin^2\theta \phi^2)\biggr)$$
in which the scaling factor $a(t)$ is squared. I cannot see any reason given for this so far, is this for dimensional reasons or is there a more important reason?

REPLY [0 votes]: Updating to give the answer from @AccidentalFourierTransform

a  is at this point arbitrary, so it doesnt really matter. Redefine
  a~=a2 if it makes you any happy. The square is useful because it
  simplifies formulas later on (and also the factor is positive, so that
  the metric has the correct signature).


TITLE: Some questions about thick sets and syndetic sets
QUESTION [0 upvotes]: A syndetic set $S$ is a subset of the natural numbers $\mathbb{N}$ or integers $\mathbb{Z}$, having the property of "bounded gaps": that the sizes of the gaps in the sequence of natural numbers is bounded. That is to say, $S$ is a syndetic set, if there exist a positive integer $l$, such that for any $n$ , we have $\{n,n+1,\cdots, n+l\}\cap S$ is non-empty.
A thick set $T$ is a subset of the natural numbers $\mathbb{N}$ or integers $\mathbb{Z}$ that contains arbitrarily long intervals. That is, given a thick set $T$, for every $n\in\mathbb{N}$, there exist $a_n\in\mathbb{N}$ such that $\{a_n,a_n+1,\cdots,a_n+n\}\subseteq T$.
A subset of $\mathbb{N}$ or $\mathbb{Z}$ is piecewise syndetic if it is the intersection of a thick set with a syndetic set.
My questions as follows,

A set $P$ is piecewise syndetic iff for some fixed $l$, $P$ contains arbitarily long strings $a_1<a_2\cdots<a_n$ satisfying $a_{i+1}-a_i\leq l$.
If $T$ is a thick subset of $\mathbb{Z}$ and $x\in T$, then $T\backslash\{x\}$ is a thick subset, too.
Does there exist abstract/general definition about thick/piecewise syndetic set of a topological (semi)group $G$?

How to prove them or explain them?
Thanks a lot.

REPLY [3 votes]: Let's start with $2$.
Fix the size of the interval you want to find in $T\setminus\left\{x\right\}$ to be $n$, find a subinterval of $T$ of length $2n+1$, so it's easily follows that you have an interval of length at-least $n$ in $T\setminus\left\{x\right\}$.
For $3$,there are general definitions, probably they appear in Furstenberg's book. In the current terminology of Tao and Hrushovski, they probably contain words like "approximate subgroups" and things like "approximate lattices".
For $1$, the direct from left to right is clear, given such interval in a thick set, you can "sieve" it out along the syndethic subset.
For the other way around.
Look at the set of such strings for given $\ell$, define $T$ to be the union of the intervals $[a_{1},a_{n}]$, so such set is thick by definition.
Define $S$ to be the set of sieved out numbers between such strings $[a_{1},a_{n}]$, and between such intervals, pick all the numbers in $\mathbb{N}$. So $S$ is syndetic with constant $\leq \ell$.
Hence $P$ contains the intersection of $T$ and $S$, so it contains a PS set and hence PS itself.


TITLE: In the symmetric group $S_{10}$, every element of order $14$ is odd permutation.
QUESTION [1 upvotes]: Show that: In the symmetric group $S_{10}$, every element of order $14$ are odd permutations.

REPLY [2 votes]: Hint:
The only possible combination of cycles in $\;S_{10}\;$ whose lowest common multiple is $\;14\;$ is a transposition and a $\;7$-cycle , so...


TITLE: Calculating the Riemann sum $\lim_{n \to \infty} { \sum_{k=1}^{n} { (\frac{nk-1}{n^3})\sin(\frac{k}{n}) } }$
QUESTION [1 upvotes]: We need to calculate this:
$$\lim_{n \to \infty} { \sum_{k=1}^{n} { (\frac{nk-1}{n^3})\sin(\frac{k}{n}) }       }$$
So I know this is Riemann sum.
This is what I started doing:

$$\sum_{k=1}^{n} { (\frac{nk-1}{n^3})\sin(\frac{k}{n})}  = \sum_{k=1}^{n} { (\frac{k}{n^2 } - \frac{1}{n^3})\sin(\frac{k}{n})}$$

But then I noticed that we can not get $\frac{1}{n}$ outside. How do we exactly know what is the partition?

REPLY [1 votes]: Hint:
The last expression equals: $\sum_1^n \dfrac{k}{n^2} \sin \dfrac{k}{n}- \sum_1^n \dfrac{1}{n^3}\sin \dfrac{k}{n}$, now what is $\lim_{n \to \infty} \dfrac{1}{n^3} \sum_1^n \sin \dfrac{k}{n}$? And use Riemann tranformation on $\sum_1^n \dfrac{k}{n^2} \sin \dfrac{k}{n}$.
Use this : $\int_0^1 f(x) =\lim_{n \to \infty}\dfrac{1}{n} \sum_1^n f(x)$


TITLE: Given a "composite" norm, what polygon describes its unit ball?
QUESTION [9 upvotes]: When answering this question about finding the open unit ball $\mathscr{B} := \{ x \in \mathbb{R}^2: \| x \| < 1\}$ of the "composite" norm
$$
\| \cdot \|:
\mathbb{R}^2 \to \mathbb{R}, \
(x,y) \mapsto a \| (x,y) \|_1 + \frac{b}{2} \| (x,y) \|_{\infty}.
$$
I thought of the following question.
In the above question one has $\Omega := \mathbb{R}^2$, $a := \frac{1}{3}$ and $b := \frac{4}{3}$ but those aren't important for my question.
All that matters is $a,b > 0$, as verified in this question.
It turns out that $\mathscr{B}$ is a octagon (as intersection of two rotated squares, as they are the geometric interpretations of $\| \cdot \|_1$ and $\| \cdot \|_{\infty}$ (is that really true?), which can be seen in the diagram appended to my answer to the first mentioned question).
My question is if (and how) one can find out which shape (polygon?) $\mathscr{B}$ corresponds for a composite norm of the form
$$
\| \cdot \|
:= \sum_{k = 1}^{\infty} \alpha_k \| \cdot \|_{x_k}, \qquad \text{where }
\alpha_k \ge 0, x_k \in [1, \infty].
$$
As @CalvinKohr points out in the comments, we can normalize this representation: $\sum_{k} \alpha_k = 1$ such that the sum is well defined i.e. converges.
This question seems to be related but I don't know how the Minkowski functional would relate to this problem even though it was briefly covered in my Functional Analysis course.
It remarks that a polygon with a odd number of vertices can not occur because of the symmetry of the norm.
As you can see in the last example below, other shapes than octagons are possible.
Can $\mathscr{B}$ be another polygon with an even number of vertices?
Maybe this is related to the concept of polyhedral norms?
One special case
Cosider the norm $\mathfrak{p}_n(x,y) := \sum_{k = 1}^{n} \| (x,y) \|_{k}$.
If we graph it and intersect it with a plane $z = \ell$ for $\ell > 0$ we obtain the the shape of $\mathscr{B}$.
I graphed $\mathfrak{p}_n$ for $n \in \{1, \ldots, 5\}$ and one observes that shapes of $\mathscr{B}$ are 4-gons that "get more convex" and converge to some circle.

This suggests it might by only interesting to at norms whose $\mathscr{B}$ is a polygon i.e. $\mathscr{B}$s with straight lines. Are those just produced by $\| \cdot \|_1$ and $\| \cdot \|_{\infty}$?.

REPLY [0 votes]: In Matrix Analysis by Horn and Johnson one can find on page 337 the following characterisation:
Theorem 5.5.8
A set $B$ in a finite-dimensional real or complex vector space $V$ with positive dimension is the unit ball of a norm if and only if $B$

is compact,
is convex,
is equilibrated, that is, $x \in B \implies \alpha x \in B$ if $| \alpha | = 1$ (also see balanced set),
has 0 as an interior point.


TITLE: Integer values of difference between cube and sqaure
QUESTION [2 upvotes]: I am trying to find square integer values for
$k = a^3-b^2$ and  $\gcd(a,b) = 1$
i.e. the values of and b for which k is a perfect square.

REPLY [0 votes]: All right, I think I remember how to derive this.  First, you'll want the formula for Pythagorean triples
$$(m^2-n^2)^2+(2mn)^2=(m^2+n^2)^2$$
Now multiply both sides by $m^2+n^2$.
$$(m^2+n^2)^3=(m^2+n^2)[(m^2-n^2)^2+(2mn)^2]$$
Finally, from here, you'll want to use Brahmagupta's Identity
$$(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2=(ac-bd)^2+(ad+bc)^2$$
to yield equations in the proper form with $a=m^2+n^2$.

REPLY [0 votes]: If $a$ is such that its  prime divisors congruent to $3$ módulo $4$ appear with an even exponent, then the same is true of $a^3$. Fermat's theorem on sums of two squares implies that $a^3$ is the sum of two squares.
Edit.
The above answer does not take into account the requirement $\gcd(a,b)=1$. Let $a=p$ be a prime such that
$$p\equiv1\mod 4.$$
The $p$ can be written in a unique way as
$$
p=b^2+c^2,\quad b,c\in\mathbb{N},\quad b\,c\ne0.
$$
The formula for the number of representations of an integer as a sum of two squares shows that $p^3$ can be written as a sum of two squares in two different ways. One of them is
$$
p^3=(b\,p)^2+(c\,p)^2.
$$
Let the other one be $p^3=d^2+e^2$. Then we must have $\gcd(p,d)=\gcd(p,e)=1$. For instance
$$\begin{align*}
5^3&=2^2+11^2\\
13^3&=9^2+46^2\\
17^3&=47^2+52^2
\end{align*}$$
A similar analysis can be carried out for other integers $a$.


TITLE: Showing the set {n+1/n} is closed but {1/n} is not
QUESTION [1 upvotes]: Let $A=\{n +1/n : n=2,3,...\}$ . I want to show that this is closed.
If we show $A^c$ is open then $A$ is closed. Here $A^c = (\cup_{i=2}^{\infty} (i +1/i, i+1 + 1/(i+1))) \cup (-\infty,2.5)$ which is an arbitaru collection of open sets which is open. This A is closed.
The only doubt I have with this style of proof is that it seems to work for $A=\{1/n\}$ as well.
Because $A^c = (\cup_{i=1}^{\infty} (1/(i+1), 1/i)) \cup (-\infty,0] \cup (1,\infty) $ which is also a collection of open sets. But we know A is not closed here. Why does the argument fail here?

REPLY [0 votes]: COMMENT.- We assume $A=\{n+\dfrac 1n: n=2,3...\}$ as subset of $\mathbb R$ provided with the usual topology.
The complement $A^c$ is obviously the union of open intervals $]n+\dfrac1n,(n+1)+\dfrac{1}{(n+1)}[$ and $]\infty,2+\dfrac12[$ so it is open.
For $B=\{\dfrac1n: n=2,3,....\}$ is in its "right" part a union of open intervals including $]\dfrac12,+\infty[$. However the limit $0$ of $B$ is not an element of $B$ so the "left" part of $B^c$ cannot be defined as an open interval (if you take $I_{n+1}=]-\infty, \dfrac{1}{n+1}[\space\space$ then $\dfrac{1}{n+2}\in I_{n+1}$ so $I_{n+1}$ is not a part of $B^c$).


TITLE: Distributions - sum of random variables
QUESTION [0 upvotes]: A point $(X,Y)$ is chosen uniformly at random from the unit square ($(X,Y)\in [0,1]^2$) and the random variables are $X$ - the x coordinate and $Y$ - the y coordinate.
Now of course X and Y have uniform distributions but how can we find the density of the random variable $X+Y$?
I've been struggling on this.

REPLY [0 votes]: There are various methods to derive this.
The graphical method is simply to note that the density function $f_{X+Y}(z)$ will be proportional to the length of the intersection of the line $x+y=z$ and the interior of the unit square.

 $$f_{X+Y}(z) = z\,\mathbf 1_{0\leq z< 1}+(2-z)\,\mathbf 1_{1<z\leq 2}$$


text:
\begin{document}

\pagenumbering{arabic} \setcounter{page}{1}

\title{Breaking the 6/5 threshold for sums and products modulo a prime}

\author{G. Shakan, I. D. Shkredov}

\address{Department of Mathematics \\
University of Illinois \\
Urbana, IL 61801, U.S.A.}
\email{shakan2@illinois.edu}

\address{ Steklov Mathematical Institute\\
ul. Gubkina, 8, Moscow, Russia, 119991 \\
and
\\
IITP RAS  \\
Bolshoy Karetny per. 19, Moscow, Russia, 127994\\
and
\\
MIPT \\
Institutskii per. 9, Dolgoprudnii, Russia, 141701\\}
\email{ilya.shkredov@gmail.com}

\begin{abstract}
Let $A \subset \mathbb{F}_p$ of size at most $p^{3/5}$. We show $$|A+A| + |AA| \gtrsim |A|^{6/5 + c},$$ for $c = 4/305$. Our main tools are the cartesian product point--line incidence theorem of Stevens and de Zeeuw and the theory of higher order energies developed by the second author.
\end{abstract}

\maketitle

\providecommand{\keywords}[1]{\textbf{\textit{Keywords---}} #1}

\section{Introduction}

For a finite subset $A$ of an abelian group, we define the sumset and product set via $$A+A :=\{a+b : a \in A, b \in B\}, \ \ \ AA := \{ab : a\in A , b\in B\}.$$
The Erd\H{o}s--Szemer\'edi sum--product conjecture \cite{ES} states the following. We adopt Vinogradov's notation and say $a \ll b$ when $a =O(b)$.

\begin{conj}\label{esconj}\cite{ES} Fix $\delta < 1$. For any finite $A \subset \mathbb{Z}$, one has
 $$|A+A| + |A A| \gg |A|^{1 + \delta}.$$
\end{conj}

The current state of the art progress towards Conjecture~\ref{esconj} is due to the first author \cite{Sha} building upon the works of \cite{El, So, BW, KS, KS2,Shr3, RSS}. The underlying idea in these works is a set with few sums and products to create point--line incidence structure with many incidences. This is in tension with point--line incidence bounds, for instance the well--known Szemer\'edi--Trotter theorem \cite{ST}, valid over $\mathbb{R}$.

It is expected that Conjecture~\ref{esconj} is true over $\mathbb{F}_p$ as long as $|A|$ is not too large. The first general sum--product bound in $\mathbb{F}_p$ was due Bourgain, Katz, and Tao \cite{BKT} in which they also gave the first general point--line incidence bound in $\mathbb{F}_p^2$. Since then, sum--product estimates have found applications to RIP matrices \cite{Bo, Bo2}, exponential sums \cite{BGK,Bo3}, and finite field Fourier restriction \cite{RuSh} to name just a few. Their sum--product estimate was quantitatively improved in \cite{Ga, KaSh,BG,Ru1}. Roche--Newton, Rudnev, and the second author \cite{RRS} obtained a big quantitative improvement coming from the breakthrough point--plane incidence bound of Rudnev \cite{Ru}.
\begin{theorem}\cite{RRS}\label{RRS} Let $A \subset \mathbb{F}_p$ of size at most $p^{5/8}$. Then $$|A+A| + |AA| \gg |A|^{6/5}.$$
\end{theorem}

We are able to improve upon Theorem~\ref{RRS}. We say $b \gtrsim a$ if $a = O(b \log^c |A|)$ for some $c >0$.

\begin{theorem}[Sum--product bound]\label{main} Let $A \subset \mathbb{F}_p$ of size at most $p^{3/5}$. Then
$$|A \pm A|^{35} |AA|^{26} \gtrsim |A|^{74}.$$ In particular,  $$|A\pm A| + |AA| \gtrsim |A|^{6/5 + 4/305}.$$
\end{theorem}
Thus we improve upon Theorem~\ref{RRS} by more than $1/100$. One can replace products with ratios in Theorem~\ref{main}. Also, we can switch the role of plus and times in our arguments, which allows us to interchange sums and products in Theorem~\ref{main}. For $|A| \geq p^{3/5}$, see for instance, \cite{Ga2}. The proof of Theorem~\ref{main} is entirely self--contained modulo the point--line incidence bound of Stevens and de Zeeuw \cite{SZ}.

We describe our two--step approach to Theorem~\ref{main}. First, we use the point--line incidence bound of Stevens and Zeeuw \cite{SZ} to bound the fourth order additive energy in terms of the product set. An application of Cauchy--Schwarz at this step recovers Theorem~\ref{RRS}. We then bound this fourth order energy via Theorem~\ref{main2} below to conclude the sumset is slightly larger than this application of Cauchy--Schwarz. In the second step we utilize the theory of higher energies developed by the second author \cite{SS, Sh1,Sh2}. We emphasize that this is a particularly simple instance of the operator method, which we describe in detail.

We actually give two proofs that one can improve Theorem~\ref{RRS}. The first is elementary, though quantitatively worse. We hope the similarities seen in these two proofs will further highlight the flexibility of the operator method.

In Section~\ref{Notation} we define quantities related to higher energies, provide some basic properties and examples, and introduce Theorem~\ref{main2}. In Section~\ref{incidence} we apply incidence geometry to bound a fourth order energy in terms of the product set. In Section~\ref{elementary}, we provide an elementary improvement to Theorem~\ref{RRS}. In Section~\ref{operator} we introduce the notion of operators and provide some basic properties and examples. In Section~\ref{optimized} we finish the proof of Theorem~\ref{main}. Note that Section~\ref{elementary} and Section~\ref{optimized} do not rely on each other in a fundamental way.

\section{Notation and Set--up}\label{Notation}

 Let $G$ be an abelian group and $A$ and $B$ be two finite subsets. We define a representation function $$r_{A-B}(x) := \#\{(a,b) \in A \times  B : x = a - b\} , \ \ x \in G .$$ Thus $$\sum_{x \in G} r_{A -B}(x) = |A||B|,$$ and so $r_{A-B}(x)$ is $|A||B| |A-B|^{-1}$ on average. The distribution of $r_{A-B}(x)$ depends on the additive structure of $A$ and $B$. To understand this better, it is convenient to introduce the {\em additive energy} of $A$ and $B$ is defined via

$$E^{+}(A,B) := \sum_x r_{A-B}(x)^2 = \sum_x r_{A+B}(x)^2 ,\ \ \ E^{+}(A) := E^{+}(A,A) .$$ We have the trivial bounds $|A|^2 \leq E^+(A) \leq |A|^3$. Heuristically, $E^+(A)$ is closer to $|A|^3$ when $A$ has additive structure. This is seen more clearly by the relation $$E^+(A) = \#\{(a , b , c, d) \in A^4 : a +b = c+ d\}.$$ Quantitatively, we have the following application of Cauchy--Schwarz \begin{equation}\label{CS} |A|^4 \leq E^+(A) |A+A| . \end{equation}
We now introduce the $k^{\rm th}$ order energy (we are primarily interested in $k = 2,4$): $$ E_k^{+}(A,B) := \sum_x r_{A-B}(x)^k, \ \ \ E_k^{+}(A) := E_k^{+}(A,A) .$$
We take $k=4$, and in this case the trivial bounds are $|A|^4 \leq E_4^+(A) \leq |A|^5$. As with the additive energy, $E_4^+(A)$ being close to $|A|^5$ is an indication of additive structure.
There is the following relation to additive energy via H\"{o}lder \begin{equation}\label{holder} E^+(A,B) = \sum_x r_{A-B}(x)^{4/3 + 2/3} \leq E_4^+(A,B)^{1/3} |A|^{2/3} |B|^{2/3} .\end{equation}
In particular,
$$
	E_4^{+} (A,B) \ge \frac{|A|^4 |B|^4}{|A+B|^3} \geq |A||B|,
$$
and so taking $B = \pm A$, we find the analog of  \eqref{CS} for $E^+_4(A)$ is \begin{equation}\label{E4} |A|^8 \leq E_4^+(A) |A\pm A|^3 \,.\end{equation}
Even with the optimal information $E_4^+(A) \leq |A|^4$, we can only conclude with \eqref{E4} that $|A \pm A| \geq |A|^{4/3}$.
 We have the relation $$E_4^+(A) = \#\{(a , b , c, d,e,f,g,h ) \in A^8 : a -b = c- d = e -f = g-h\}.$$
Geometrically, as in \cite[Equation 9]{MRSS}, $E_4^+(A)$ counts the number of collinear quadruples in $A \times A$ that lie on a line of the form $y = x + d$. By double counting the projections onto the coordinate axes, we find that \begin{equation}\label{quad} E_4^+(A) = \sum_{x,y,z} |A \cap (A+x) \cap (A+y) \cap (A+z)|^2.\end{equation} Indeed, $a , a+x , a+y , a+z \in A$ can be extended to a collinear quadruple in $A \times A$ on a line of slope one of the form  $$(a,b) , (a+x , b') , (a+y , b'') , (a+ z , b''') , \ \ \ b , b' , b'' , b''' \in A,$$ if and only if $b = b' + x = b'' + y = b''' + z $. One natural question is to relate $E_4^+(A)$ to lower order energies. We give one possible way to do this in Lemma~\ref{lem1} below.

We will also need the following definition, which is crucial in the proof of Theorem~\ref{main}.
\begin{defn}\label{dplus}
Let $A \subset G$ be  finite. We define  $$d_4^{+}(A) := \sup_{B \neq \emptyset}\frac{ E_4^+(A,B) }{|A| |B|^3}.$$ \end{defn}
It follows from Definition~\ref{dplus} that $$1\leq E_4^+(A) |A|^{-4} \leq d_4^{+}(A) \leq |A|.$$ All of the identities we mentioned for $E_4^+(A)$ can be generalized in a natural way for $E_4^+(A,B)$. Intuitively, the closer $d_4^{+}(A)$ is to $|A|$, the more additive structure $A$ has. Indeed $d_4^+(A)$ is a fourth moment analog of the additive energy of a set, where we are allowed flexibility in choosing $B$. The next two key examples highlight the subtle difference in working with $d_4^+(A)$ as opposed to $E_4^+(A)$. We take $x \asymp y$ to mean $x \ll y$ and $x \gg y$.

\begin{exam}[Small progression and many generic elements] Let $n,m \geq 1$ be fixed integers. Let $$A= \{1 , \ldots , n\} \cup \{n , \ldots , n^m\} , \ \ \ n^5 \asymp m^4$$ be
	 the union
	 of an arithmetic progression with a disassociated set.  Thus $|A| \asymp m$. We have $$E_4^+(A)|A|^{-4} \asymp 1.$$On the other hand, letting $B = \{1 , \ldots , n\}$, we find $$E_4^+(A,B) |A|^{-1} |B|^{-3} \asymp n^2 m^{-1} \asymp m^{3/5} \asymp |A|^{3/5}.$$ Thus $d_4^+(A) \gg |A|^{3/5}$, which is significantly larger than $E_4^+(A) |A|^{-4}$. \end{exam}

The previous example is important in the paper of the second author \cite{Sh2}. In the next example we will see the quantity $d_4^+(A)$ is large because it is contained in a set with additive structure, rather than containing a set with additive structure in the previous example.

\begin{exam}[Dense subset of interval]\label{example} Consider a random $A \subset \{1 , \ldots , n\}$ where each element is chosen independently and uniformly with probability $p > n^{-1/2}$. We have $|A| \sim pn$ with high probability. Let $B = \{1 , \ldots , n\}$. It follows from Chernoff's inequality (for instance, Chapter 1 of \cite{TV}) and the union bound, that every $x$ with $r_{B-B}(x) \geq  p^{-2} \log n$ satisfies
$$r_{A-B}(x) \sim p \cdot r_{B-B}(x) , \ \ \ \  r_{A-A}(x) \sim p^2 \cdot  r_{B-B}(x) .$$
This implies $$\frac{ E_4^+(A,B) }{|A| |B|^3} \sim p^2|A|, \ \  \frac{ E_4^+(A) }{|A|^4} \sim p^3|A|  .$$ In this example $d_4^+(A)$ is larger than what is predicted by the fourth order energy, where we only allow $B=A$ in Definition \ref{dplus}. One can show $d_4^+(A) \sim p^2 |A|$.
\end{exam}

We note that $B$ cannot be too large or small in Definition~\ref{dplus}.

\begin{remark}\label{size} Observe that the supremum in Definition \ref{dplus} is achieved for some $$ |B| \leq |A|^{3/2}.$$ Indeed for $|B| \geq |A|^{3/2}$, we have $$\frac{E_4^+(A,B) }{|A||B|^3} \leq \frac{|A|^3}{|B|^2} \leq 1 \leq d^+(A).$$
\end{remark}
From \eqref{E4} we have the following Cauchy--Schwarz \begin{equation}\label{CS4} |A|^4 \leq |A\pm A|^3 d_4^+(A) . \end{equation}

So \eqref{CS4} is \eqref{E4} for the quantity $d_4^+(A)$. One of our goals will be to improve upon \eqref{CS4}, utilizing the flexibility in the choice of $B$ in Definition~\ref{dplus}.
\begin{theorem}[Small energy implies large sumset]\label{main2} Let $A$ be a subset of an abelian group. Then $$|A\pm A| \gtrsim |A|^{48/35} /d_4^+(A)^{13/35} $$
\end{theorem}

To see that this improves \eqref{CS4}, one just needs to check $48/35 > 4/3$. Theorem~\ref{main2} has limitations. In light of Example~\ref{example}, the best one can hope for is $$|A+A| \gtrsim |A|^{3/2} d_4^+(A)^{-1/2}.$$ This unproven bound, combined with Proposition~\ref{energyreduction} below, would give an Elekes \cite{El} type bound for the sum--product problem over $\mathbb{F}_p$.

\section{Reduction to an energy estimate via incidence geometry}\label{incidence}

The main purpose of this section is to show if the product set of $A \subset \mathbb{F}_p$ is small then $d_4^+(A)$ is small.

\begin{prop}[Incidence bound]\label{energyreduction} Let $A \subset \mathbb{F}_p$ such that $|A| < p^{3/5}$. Then $$d_4^+(A) \lesssim |AA|^2 |A|^{-2}.$$
\end{prop}
The key input in the proof of Proposition~\ref{energyreduction} is the point--line incidence bound of Stevens and de Zeeuw \cite{SZ}. Theorem~\ref{main} then follows immediately upon combining Proposition~\ref{energyreduction} and Theorem~\ref{main2}. On the other hand, combining Proposition~\ref{energyreduction} with \eqref{CS4} recovers Theorem~\ref{RRS}.

\begin{remark} Proposition~\ref{energyreduction} is why we are required to introduce higher order energies of the form in Definition~\ref{dplus}. We provide some context. This idea originated from a paper of Schoen and the second author \cite{SS}. We say a finite $A \subset \mathbb{R}$ is convex if it has increasing consecutive differences. It was known for convex sets that  $$\max_{B \neq \emptyset} \frac{E_3^+(A,B)}{|A|^{} |B|^{2}} \lesssim 1.$$ They were able to use this to show that $$|A+A| \gtrsim |A|^{3/2 + \delta}, \ \ \ \text{for some }   \delta > 0,$$ thus breaking the ``3/2--barrier."
\end{remark}

We will use an incidence theorem specialized for cartesian products due to Stevens and de Zeeuw \cite[Theorem 4]{SZ}, building work in  \cite{BKT, Jo}. The exact statement we use is a slight modification of it appearing in work of Murphy and Petridis (see also \cite[Lemma 12]{Shr5}).

\begin{theorem}\label{SZ} \cite[Theorem 7]{MP}
    Let $A,B \subseteq \F_p$ be sets. Let $\mathcal{P} = A\times B$ and $ \mathcal{L}$ be a collection of lines in $\F^2_p$.
    Then
    \begin{equation}
    \mathcal{I}(\mathcal{P}, \mathcal{L}) \ll |A|^{3/4} |B|^{1/2} |\mathcal{L}|^{3/4} + |\mathcal{L}| + |A| |B|  + \frac{|A| |B| |\mathcal{L}|}{p} \,.
    \end{equation}
\end{theorem}

Theorem~\ref{SZ} is most naturally interpreted as a fourth moment estimate, that is a $d_4^+(A)$ estimate. One can see this by the exponent $3/4$ on $\mathcal{L}$ in the conclusion. This differs from the real case, in which Szemer\'edi--Trotter gives an exponent $2/3$, which is most naturally a third moment estimate. This was taken advantage of in recent work of the first author \cite{Sha} to improve the Balog--Wooley decomposition \cite{BW}.

\begin{proof}[Proof of Proposition~\ref{energyreduction}]
Let $B$ be a set obtaining the maximum in Definition~\ref{dplus}. By a dyadic decomposition, there is a $\tau \geq 1$ such that $$E_4^+(A,B) \lesssim |D_{\tau}| \tau^4 ,  \ \ D_{\tau} = \{x \in A-B : r_{A-B}(x) \geq \tau\}.$$ Thus to prove Proposition~\ref{energyreduction}, it is enough to show \begin{equation}\label{enough} |D_{\tau}| \tau^4 |A|^{-1} |B|^{-3} \ll |AA|^{2} |A|^{-2}. \end{equation} We plan to apply Theorem~\ref{SZ} to the point set $$D_{\tau} \times AA$$ and the $|B||A|$ lines of the form (without loss of the generality one can suppose  that $0\notin A$)
$$\{(u , v) \in \mathbb{F}_p^2 : v = \frac{u}{r} - b \}, \ \ \ r \in A , \ b \in B.$$
Observe that for any $a \in A$ there are $|A|$ solutions to the equation $$a = q/r , \ \ q \in AA , \ r \in A.$$ Applying Theorem~\ref{SZ}, we obtain that

\begin{align*}
|A||D_{\tau}| \tau &\leq |A| \#\{(x , a , b) \in D_{\tau} \times A \times B : x = a -b\} \\
& \leq \#\{(x , u , r, b) \in D_{\tau} \times AA \times A  \times B : x = u/r -b\} \\
& \ll |D_{\tau}|^{3/4} |AA|^{1/2} |A|^{3/4} |B|^{3/4} + |A| |B| + |D_{\tau}| |AA| + |A||B||D_{\tau}||AA| p^{-1}.
\end{align*}
Thus $|A||D_{\tau}| \tau$ must be at most a constant times one of the terms on the right hand side.
In the main case, that is the first term in the bound dominates, we have
$$ |A| \tau |D_{\tau}| \ll |D_{\tau}|^{3/4} |AA|^{1/2} |A|^{3/4} |B|^{3/4},$$ which after simplifying gives \eqref{enough}.

We now handle the error terms. We will use the following two inequalities repeatedly \begin{equation}\label{Dtau} |D_{\tau}| \tau \leq |A||B| ,\end{equation}
\begin{equation}\label{tau} \tau \leq |A| , |B|. \end{equation}
Suppose $$|A||D_{\tau}| \tau \ll |A| |B|.$$ Then we have $$ |D_{\tau}| \tau \ll |B|,$$ which combined with \eqref{tau} gives \eqref{enough} via  $$\frac{|D_{\tau}| \tau^4}{|A| |B|^3} \ll \frac{\tau^3 |B|}{|A| |B|^3} \ll 1 \leq |AA|^2 |A|^{-2}.$$
Next, we suppose $|A||D_{\tau}| \tau  \ll |D_{\tau}| |AA|$ and so $|A|\tau \ll |AA|$. Combining with \eqref{tau} and \eqref{Dtau}, we find
$$ \frac{|D_{\tau}| \tau^4}{|A| |B|^3} \ll |AA|^2 |A|^{-2} \frac{ |D_{\tau}| \tau^2 }{|A| |B|^3} \leq |AA|^2 |A|^{-2} |B|^{-1},$$ which is better than \eqref{enough}.

We may assume \begin{equation}\label{AA} |AA| \leq |A|^{3/2}, \end{equation} for otherwise \eqref{enough} follows immediately from $|D_{\tau}| \tau^4 |A|^{-1} |B|^{-3} \leq |A|$.

Suppose that $|A||D_{\tau}| \tau \ll  |A||B||D_{\tau}||AA| p^{-1}$ and so $p \tau \ll |B| |AA|$. We may suppose $\tau^3 \geq |B|^2 |AA|^2 |A|^{-2}$, since otherwise we may use \eqref{Dtau} to obtain \eqref{enough} via $$|D_{\tau}| \tau^4 |A|^{-1} |B|^{-3} \leq \tau^3 |B|^{-2} \leq |AA|^{2} |A|^{-2}.$$ Then
 $$|AA|^2|A|^{-2} |B|^2p^3 \leq \tau^3 p^3 \ll |B|^3 |AA|^3,$$
which simplifies to $$p^3 \ll |AA| |B||A|^2 \leq |A|^5,$$ by \eqref{AA} and Remark~\ref{size}. This case cannot happen by our assumption $|A| < p^{3/5}$ in Proposition~\ref{energyreduction}.

Thus in all possible cases \eqref{enough} holds and so Proposition~\ref{energyreduction} follows.

\end{proof}

We end this section with a summary of the proof of Proposition~\ref{energyreduction}. If $d_4^+(A)$ is large, then the equation $$x = a - b , \ \ x \in D , \  a \in A, \  b\in B,$$ has many solutions for some choices of $D$ and $B$. On the other hand, if $|AA|$ is small, then we may efficiently write $a = q/r$ (an important case to keep in mind is when $A$ is a multiplicative subgroup). Thus there are many solutions to $x = q/r - b$, which is in contrast with the Stevens and de Zeeuw point--line incidence bound.

\section{Elementary energy estimates}\label{elementary}

Our main goal is to use elementary methods, adopted from \cite{SS}, to improve upon \eqref{CS4}, which combined with Proposition~\ref{energyreduction} improves upon the sum--product estimate in Theorem~\ref{RRS}. Wo only handle the ``minus" case, since the ``plus" case is a bit more technically involved (see \cite[Theorem 1]{SS}).

We need following notation for $x \in G$,
\begin{equation}\label{translate} A_x : = A \cap (A+x).\end{equation} Thus $$|A_x| = r_{A - A}(x).$$

The following lemma allows us to pass from fourth order energy to additive energy of subsets of the form \eqref{translate}. This is a special case of \cite[Lemma 2.8]{SV}.
\begin{lemma}\label{lem1} Let $A$ be a subset of an abelian group $G$. Then $$E_4^+(A) = \sum_{x , w \in G} E^+(A_x , A_w).$$
\end{lemma}

\begin{proof}
By \eqref{quad}, we have \begin{align*}E_4^+(A) &= \sum_{x,y,z} |A \cap (A+x) \cap (A+y) \cap (A+z)|^2 \\
& = \sum_{x ,y,z} |A_x \cap (A_{z -y} + y)|^2
 = \sum_{x, w,y} |A_x \cap (A_w + y)|^2 \\
& = \sum_{x,w,y}  r_{A_x - A_w}(y)^2 = \sum_{x , w} E^+(A_w , A_x)\end{align*}
\end{proof}

The next lemma asserts if the fourth energy of $A$ is small, then many of the sumsets from \eqref{translate} are large. This is a special case of \cite[Lemma 2.6]{SV}.

\begin{lemma}\label{energy}Let $P$ be any subset of $A-A$. Then $$\left(\sum_{x \in P} |A_x| \right)^4 \leq E_4^+(A)\sum_{x,w \in P} |A_x \pm A_w|  .$$
\end{lemma}

\begin{proof} The proof is Lemma~\ref{lem1} and two applications of  Cauchy--Schwarz, the first of which being \eqref{CS}. We have \begin{align*} \left(\sum_{x \in P} |A_x| \right)^4 & = \left(\sum_{x ,w \in P} |A_x||A_w| \right)^2 \leq  \left(\sum_{x ,w \in P} |A_x \pm A_w|^{1/2} E^+(A_x , A_w)^{1/2} \right)^2 \\
& \leq \sum_{x ,w \in P} |A_x \pm A_w| \sum_{x,w}  E^+(A_x , A_w) = E_4^+(A)  \sum_{x ,w \in P} |A_x \pm A_w|
\end{align*}
\end{proof}

We remark that we could apply Lemma~\ref{energy} with $P = A-A$ along with the trivial bound $$|A_x - A_w| \leq |A - A|,$$ to obtain $$|A|^8 \leq E_4^+(A) |A-A|^3.$$ Combining this with the following implication of Definition~\ref{dplus} \begin{equation}\label{triv} E_4^+(A) \leq d_4^+(A) |A|^4, \end{equation} we are lead back to the bound \eqref{CS4}. We improve upon this argument with Katz--Koester inclusion \cite{KK}.

\begin{prop}\label{diff} Let $A$ be a finite subset of an abelian group $G$. Then $$|A-A| \gg \frac{|A|^{15/11}}{d_4^+(A)^{4/11}}.$$
\end{prop}

This is an improvement on \eqref{CS4}. Combining this with Proposition~\ref{energyreduction} gives the difference--product estimate $$|A-A| + |AA| \gg |A|^{6/5 + 1/95}.$$

\begin{proof} Let $$P = \{x \in A -A : r_{A-A}(x) \geq |A|^2 / (2 |A-A|) \},$$ be a set of popular differences. Then $$\sum_{x \in P} r_{A-A}(x) \geq |A|^2 / 2.$$ By Lemma~\ref{energy} and \eqref{triv} we find \begin{equation}\label{inter}|A|^8 \ll E_4^+(A) \sum_{x ,w \in P} |A_x - A_w| \leq d_4^+(A) |A|^4 \sum_{x ,w \in P} |A_x - A_w|  .\end{equation}
Let $D= A-A$. Then Katz--Koester inclusion yields $$A_x - A_w \subset D \cap (D+x) \cap (D - w) \cap (D+ x - w).$$ Thus we have \begin{align*}\sum_{x ,w \in P} |A_x - A_w| & \leq \sum_{x ,w \in P}  |D \cap (D+x) \cap (D -w) \cap (D+ x -w)| \\ & = \sum_{x , w \in P} |D_x \cap (D_x  -w)| \leq \sum_{x \in P} |D_x|^2.\end{align*}
Combining this with \eqref{inter}, we have  \begin{equation}\label{setversion} |A|^4 d_4^+(A)^{-1} \leq E^+(D) \end{equation}
Now the trivial bound is $$\sum_{x \in P} |D_x|^2 \leq |D|^3,$$ which upon combing with \eqref{setversion} would yield \eqref{CS4}. We can improve upon this when $d_4^+(A)$ is small. Using $x \in P$ and H\"{o}lder via \eqref{holder}, we find \begin{align*} \sum_{x \in P} |D_x|^2 & \leq |D| \sum_{x \in P} r_{D-D}(x) \ll \frac{|D|^2}{|A|^2} \sum_{x \in P} r_{D-D}(x) r_{A-A}(x) \leq\frac{|D|^2}{|A|^2}  E^+(A,D) \\ & \leq \frac{|D|^2}{|A|^2} E_4^+(A, D)^{1/3} (|A| |D|)^{2/3} \leq \frac{|D|^2}{|A|^2} (d_4^+(A) |A| |D|^3)^{1/3} (|A| |D|)^{2/3} \end{align*}
We combine this with \eqref{setversion} to obtain $$ \frac{|A|^{4}}{d_4^+(A)} \leq d_4^+(A)^{1/3} |A|^{-1} |D|^{11/3}.$$ Simplifying gives Proposition~\ref{diff}.

\end{proof}

\begin{remark} In the proof of Proposition~\ref{diff}, we used the identity $$E^+(A,D) = \sum_{x} r_{A-A}(x) r_{D-D}(x),$$ which is an consequence of $$a - a' = d  - d' \ \  \text{if and only if}  \ \ a - d = a' - d'.$$ There is no such identity for higher energies.
\end{remark}

\section{Operator method basics}\label{operator}

We now introduce the notions from the theory of operators and higher order  energies, developed by the second author \cite{Sh1, Sh2}. We do not require much, but we provide some context. This theory was already used to improve sum--product estimates over the real numbers \cite{KS, KS2, Sha}. The results we need are much simpler than the real case, for a reason we will explain below. We will use some basic facts from linear algebra, which can be found in \cite{HJ}.

 For two functions $f,g :G \to \mathbb{C}$ with finite support, we define the convolution of $f$ and $g$ via \begin{equation*}\label{f:convolutions}
(f*g) (x) := \sum_{y\in G} f(y) g(x-y)\,, \ \ \ (f \circ g) (x) := \sum_{y \in G} f(y) g(x+y).
\end{equation*}
Thus $$r_{A+B}(x) = 1_A * 1_B(x) , \ \ \ r_{A-B}(x) = 1_A \circ 1_B(x).$$
We first want to illustrate why the study of operators is a natural one in additive combinatorics. To this end, we interpret the set $A$ as a {\em convolution operator}, $K_A$ or $\widetilde{K}_A$, via $$K_A(f)(x) := 1_A * f (x) , \ \ \ \widetilde{K}_A(f)(x) := 1_A \circ f (x).$$ All of the quantities we have previously defined can be given in terms of $\widetilde{K}_A$: \begin{align*}E^+(A) &= ||\widetilde{K}_A( 1_A)||_2^2 , \ E_4^+(A) = ||\widetilde{K}_A (1_A)||_4^4, \\ ||\widetilde{K}_A(1_B)||_1 &= |A||B|, \ |A-B| =| {\rm supp}( \widetilde{K}_A (1_B)| \\ d_4^+(A) &= |A|^{-1} ||\widetilde{K}_A||_{\ell^4 \to \ell^{4/3}}^3 , \  r_{A-B}(x) = \widetilde{K}_A (1_B)(x) .\end{align*} Indeed $\widetilde{K}_A(1_0) = 1_A$, and so we can recover $A$ from $\widetilde{K}_A$. Thus there is no loss in generality in considering $\widetilde{K}_A$ in place of $A$. We also need a {\em local} version of $\widetilde{K}_A$, given by $$\widetilde{K}_A^A (f)(x) : = 1_A(x) \widetilde{K}_A(f)(x).$$ Again $\widetilde{K}_A^A(1_0)(x) = 1_A(x)$, so we may recover $A$ from $\widetilde{K}_A^A$. A priori, $\widetilde{K}_A^A$ is not a finite dimensional operator, but from the definition we see \begin{equation}\label{KA} \widetilde{K}_A^A(1_z) (x)= 1_A(x)1_{A-z}(x).\end{equation} This can be nonzero only if $z \in A-A$ and so we may interpret $\widetilde{K}_A^A$ as a $A \times (A-A)$ matrix with the $(x,z)$ entry given in \eqref{KA}.

Given a function $g : G \to \mathbb{C}$, we let $T_A^g$ and $\widetilde{T}_A^g$ be the $|A| \times |A|$ square matrices defined by $$T_A^g(x,y) := g(x-y) 1_A(x) 1_A(y), \ \ \ \widetilde{T}_A^g(x,y) := g(x+y) 1_A(x) 1_A(y).$$ One important example is $g(z) = r_{A-A}(z)$. From \eqref{KA}, we see that $$T_A^{r_{A-A}} = \widetilde{K}_A^A (\widetilde{K}_A^A)^*,$$ where $(\widetilde{K}_A^A)^*$ is the adjoint of $\widetilde{K}_A^A$. Thus $T_A^{r_{A-A}}$ is a non-negative, self adjoint operator.

\begin{exam}Let us compute $T_A^{r_{A-A}}$ two examples. First take $S$ to be a Sidon set. Then $$T_S^{r_{S-S}} = (|S| - 1) I + J,$$ where $J$ is the all ones matrix. Now, suppose that $H$ is a subgroup of $G$. In this case $$T_H^{r_{H-H}} = |H| J.$$ The eigenvalues for $T_S^{r_{S-S}}$ are $$2|S| -1 , |S| -1 , \ldots , |S|-1,$$ while the eigenvalues for $T_H^{r_{H-H}}$ are $$|H|^2, 0 , \ldots , 0.$$ Thus the eigenvalues of $T_A^{r_{A-A}}$ for sets with additive structure are localized.
\end{exam}

One can check that adding a few disassociated elements to $H$ in the previous example does not greatly alter the eigenvalues. Before the next example, we recall some facts from linear algebra. Let $M$ be an $n \times n$ Hermitian matrix with eigenvalues $|\mu_1| \geq \ldots \geq |\mu_n|$. Then $$|\mu_1| = \sup_{||v||_2 = 1} |\langle Mv , v \rangle|,  \ \ \ {\rm trace}(M^k) = \sum_{j=1}^n \mu_j^k.$$

\begin{exam} Let us give a basic demonstration on how to use the operator $T_A^{r_{A-A}} $ to obtain higher energy bounds. Note that $T_A^{r_{A-A}}$ is self adjoint and non--negative and so it has $|A|$ real eigenvalues $\mu_1 \geq \cdots \geq \mu_{|A|} \geq 0$. Thus $$\mu_1^2 \leq \sum_{j=1}^{|A|} \mu_j^2 \leq {\rm trace}({(T_A^{r_{A-A}}})^2) = \sum_{x,y \in A} r_{A-A}(x-y) r_{A-A}(y-x) = E_3^+(A).$$ On the other hand, we may take the unit vector $v : = |A|^{-1/2} (1 , \ldots , 1)^T$ and see that $$\mu_1 \geq \langle T_A^{r_{A-A}} v , v \rangle = E^+(A) |A|^{-1}.$$ Putting this together, we obtain $$E^+(A)^2 \leq E_3^+(A) |A|^2,$$ which recovers an application of Cauchy--Schwarz. The situation that arises after will be more complicated combinatorially (we take a fourth power of a matrix), but is in a similar spirit to this example.
\end{exam}

We now introduce a different choice of $g$. Computing higher powers of $T_A^g$ and $\widetilde{T}_A^g$ for this choice of $g$ gives rise to other combinatorial quantities. \begin{remark}\label{Pidentity} Let $P \subset A+A$ and consider $\widetilde{T}_A^{1_P}$.  Note that $\widetilde{T}_A^{1_P}$ is self--adjoint, but not non--negative in general. Let $|\mu_1| \geq \dots \geq |\mu_{|A|}|$ be the eigenvalues. For the unit vector $v = |A|^{-1/2}(1 , \ldots , 1)$, we have $$|\mu_1| \geq \langle \widetilde{T}_A^{1_P} v , v \rangle = |A|^{-1} \sum_{x , y  \in A} 1_P(x+y) =  |A|^{-1} \sum_{z \in P} r_{A+A}(z).$$  Thus for any integer $k \geq 1$, we have
\begin{equation}\label{trace} \left( |A|^{-1} \sum_{z \in P} r_{A+A}(z) \right)^{2k} \leq  \mu_1^{2k} \leq \sum_{j=1}^{|A|} \mu_j^{2k} \leq  {\rm trace}((\widetilde{T}_A^{1_P})^{2k}). \end{equation}
The right hand side of \eqref{trace} can be written as $$\sum_{x_1 , \ldots , x_{2k} \in A} 1_P(x_1+x_2) \cdots 1_P(x_{2k-1} + x_{2k}) 1_P(x_{2k} + x_1).$$ See Lemma~\ref{eigen} below for one possible estimate of this quantity.
\end{remark}

For a finite set $A \subset G$ we define another natural notion of higher order energy via \begin{align*} T_k(A) & = \#\{(a_1 , \ldots , a_{2k} )\in A^{2k} : a_1 + \ldots + a_k = a_{k+1} + \ldots + a_{2k}\} \\ &= \int_{\mathbb{R}/ \mathbb{Z}} |\sum_{a \in A} e^{2 \pi i a \theta} |^{2k} d \theta.\end{align*}
Higher powers of $\widetilde{T}_A^{1_P}$ in \eqref{trace} give rise combinatorial quantities involving higher order energies of $A$.

\begin{lemma}\cite[Proposition 31]{Sh2}\label{eigen} Let $k\geq 2$ be a power of two and $A, B \subset G$ be two finite sets. Then for any $P \subset A - B$, one has

$$\left(\sum_{x\in P} r_{A-B}(x)\right)^{4k} \leq |A|^{2k} |B|^{2k} T_k(P) \sum_x r_{A-A}(x)^k r_{B-B}(x)^k.$$
\end{lemma}

We only need a special case of Lemma~\ref{eigen}, and we will provide a proof in this special case in Lemma~\ref{energy} below. We state Lemma~\ref{eigen} it here to illustrate the generality of the operator method. The case $B = A$ is easier as one can prove Lemma~\ref{eigen} with the spectral theory of self--adjoint operators rather than singular value decomposition. In the case $B= A$, $P=A-A$, and $k=2$, Lemma~\ref{eigen} reduces to \begin{equation}\label{first} |A|^8 \leq E_4^+(A) E^+(P).\end{equation} We show that if $A$ has a small product set than we have non--trivial bounds for both quantities on the right hand side of \eqref{first}. Actually we already saw this inequality in \eqref{setversion}, but we need Lemma~\ref{eigen} to obtain a {\em statistical version}, where $P$ is allowed to be a set of popular differences.

\section{Optimized energy estimates}\label{optimized}

Our main goal is to prove Theorem~\ref{main2} and improve upon \eqref{CS4}. The proof requires two separate parts. The first is a simple application of the operator method developed by the second author. This is a special case of Lemma~\ref{eigen}, but we provide a proof here.

\begin{lemma}\label{energy}\cite[Proposition 31]{Sh2}
	Let $A$ be a subset of an abelian group and $P\subseteq A-A$.
	Then
$$
	\left( \frac{\sum_{x\in P} r_{A-A} (x)}{|A|}\right)^{8} \leq E^{+}_{4} (A) E^+ (P) \,.
$$
	Similarly, for any $P\subseteq A+A$ the following holds
$$
\left( \frac{\sum_{x\in P} r_{A+A} (x)}{|A|}\right)^{8} \leq E^{+}_{4} (A) E^{+} (P) \,.
$$
\end{lemma}

The idea is to bound the trace of the fourth power of a matrix in two ways: {\em spectrally} and {\em combinatorially}.

Lemma~\ref{energy} should be compared with \eqref{setversion}. This is a ``statistical version" of a set inequality, which the operator method is suitable for. Actually, one can modify the application of Katz--Koester given above to prove Lemma~\ref{energy} for difference sets, but it is unclear how to do so for sumsets.

We will use the following identity, valid for finite $P$, \begin{equation}\label{energyP} \sum_{\alpha , \beta , \gamma} 1_P(\alpha) 1_P(\alpha - \beta) 1_P(\gamma - \beta) 1_P(\gamma) = E^+(P).\end{equation}
Indeed, $$\sum_{\alpha} 1_P(\alpha) 1_P(\alpha - \beta) = r_{P-P}(\beta) , \ \ \ \sum_{\gamma} 1_P(\gamma - \beta) 1_P(\gamma) = r_{P-P}(\beta).  $$

\begin{proof}
We prove the plus statement, the minus being easier. Consider the matrix $M = \widetilde{T}_A^{1_P}$ defined by $$M(x,y) = 1_A(x) 1_A(y) P(x+y).$$  Note that $M$ is self adjoint and so all of its eigenvalues are real. By Remark~\ref{Pidentity}, we have that the absolute value of the largest eigenvalue is at least $|A|^{-1} \sum_{z \in P} r_{A+A}(z)$, and so the trace of $M^4$ is at least $$\left( |A|^{-1} \sum_{z \in P} r_{A+A}(z)\right)^4.$$
On the other hand the trace of $M^4$ is equal to \begin{equation}\label{trace2}\sum_{x,y,z,w \in A} 1_P(x + y) 1_P(y+z) 1_P (z+ w) 1_P(w+x).\end{equation}
We change variables, leaving $x$ unchanged, to $$\alpha = x + y, \beta = x - z , \gamma = x + w .$$ Thus $x \in A \cap (\alpha - A) \cap (\beta +A) \cap (  \gamma - A)$ and so we find that \eqref{trace2} is

\begin{align*} =&\sum_{\alpha, \beta, \gamma} 1_P(\alpha) 1_P(\alpha - \beta) 1_P (\gamma - \beta) 1_P(\gamma)|A \cap (\alpha - A) \cap (\beta + A) \cap (\gamma - A)| \\
\leq & \left( \sum_{\alpha, \beta, \gamma} 1_P(\alpha) 1_P(\alpha - \beta) 1_P (\gamma - \beta) 1_P(\gamma) \sum_{\alpha, \beta, \gamma} |A \cap (\alpha - A) \cap (\beta + A) \cap (\gamma - A)|^2 \right)^{1/2}  \\
=& E(P)^{1/2}  \left( \sum_{\alpha, \beta, \gamma} |A \cap (\alpha - A) \cap (\beta + A) \cap (\gamma - A)|^2 \right)^{1/2} \end{align*} using Cauchy--Schwarz and then \eqref{energyP}. Now we want to use \eqref{quad}, but there is a sign issue. It turns out we still can. In a similar manner to Lemma~\ref{lem1}, recalling the definition in \eqref{translate}, we have
\begin{align*} & \sum_{\alpha, \beta, \gamma} |A \cap (\alpha - A) \cap (\beta + A) \cap (\gamma - A)|^2 = \sum_{\beta ,\alpha , \gamma} |A_{\beta} \cap (-A_{\gamma - \alpha} + \alpha)|^2 \\ &=
\sum_{\beta, w} E^+(A_{\beta} , - A_{w}) =  \sum_{ \beta , w} E^+( A_{\beta} , A_w) \\ &   = \sum_{\alpha , \beta , \gamma} |A \cap (A + \alpha) \cap (A + \beta) \cap (A + \gamma)|^2 \end{align*}
Thus by \eqref{quad}, we find that \eqref{trace2} is $\leq E_4^+(A)^{1/2}E^+(P)^{1/2}$, as desired.
\end{proof}

\begin{remark} In the sum--product problem over $\mathbb{R}$, third order energies are the object of study. In this case, it would be advantageous to modify Lemma~\ref{energy} by taking a third power of $M$. One is presented with the difficulty that the third powers of the eigenvalues can be negative and one cannot bound the trace of $M^3$ from below by the cube of the largest eigenvalue, as in \eqref{trace}. This makes the analysis harder (see \cite[Theorem 11]{Sh4}).
\end{remark}

We are now ready to prove Theorem~\ref{main}. Before we do so, let us reevaluate our position after Lemma~\ref{energy}. Taking $P = A+A$ in Lemma~\ref{energy}, and using \eqref{triv} we find that $$|A|^4 d_4^+(A)^{-1} \leq E^+(P) \leq |A+A|^3,$$ where we used the trivial bound $E^+(P) \leq |P|^3$ in the last inequality. Simplifying, we are lead back to \eqref{CS4}. Any nontrivial improvement over this trivial bound will give us an improvement over \eqref{CS4}. There is not a unique way to proceed here, as we saw in Section~\ref{elementary}.  We are interested in the best quantitative bounds so we present the following argument. The idea is to write $P +P= (A+A) + P = A + (A+P)$, and then bound this by taking $B = A+P$ in Definition~\ref{dplus}. We then bound the size of $A+P$ by using Definition~\ref{dplus} again with $B = P$.
\begin{proof}[Proof of Theorem~\ref{main2}:]
We only prove the plus version, the minus version following in a similar manner. Let $$P = \{x \in A+A : r_{A+A}(x) \geq 2^{-1} |A|^2 |A+A|^{-1}\}.$$ Thus $$\sum_{x\in P} r_{A+A}(x) \geq |A|^2 / 2.$$We apply Lemma~\ref{energy} and \eqref{triv} to obtain $$|A|^4 d_4^+(A)^{-1} \ll E^+(P).$$
By our choice of $P$, we have $$|A|^2 |A+A|^{-1}r_{P+P}(x) \ll  r_{A+A+P}(x),$$ and so
\begin{equation}\label{inter2}E^+(P) \ll \frac{|A+A|^2}{|A|^4} \sum_x r_{A+A + P}(x)^2.\end{equation}
By a dyadic decomposition, we find a $\Delta \geq 1$ such that
$$ \sum_x r_{A+A + P}(x)^2 \lesssim \Delta^2 \sum_x r_{A+T}(x)^2 ,  \ \ \ T = \{x : \Delta \leq r_{A+P}(x)  \leq 2 \Delta \} . $$
Thus \eqref{inter2} is $$\ll  \frac{|A+A|^2}{|A|^4}\Delta^2 \sum_x r_{A+T}(x)^2 \leq \frac{|A+A|^2}{|A|^4}\Delta^2 E_4^+(A,B)^{1/3} |A|^{2/3} |T|^{2/3} ,$$ by H\"{o}lder's inequality as in \eqref{holder}. By Definition~\ref{dplus}, this is $$\ll \frac{|A+A|^2}{|A|^4}\Delta^2 d_4^+(A)^{1/3} |A| |T|^{5/3} = \frac{|A+A|^2}{|A|^4}d_4^+(A)^{1/3} |A| (\Delta |T|)^{14/9} (\Delta^4 |T|)^{1/9}.$$
Now from the definition of $T$, we have that $$|T| \Delta^4 \leq \sum_x r_{A +P}(x)^4 \leq d_4^+(A) |A| |P|^3, \ \ |T| \Delta \leq \sum_x r_{A+P}(x) \leq |A||P|\,, $$ and so putting this altogether we obtain $$|A|^4 d_4^+(A)^{-1} \ll E^+(P) \lesssim |A+A|^2 d_4^+(A)^{4/9} |A|^{-4/3} |P|^{17/9}.$$ Using $P \subset A+A$ and simplifying gives Theorem~\ref{main2}.

\end{proof}

It is interesting to note that the techniques in Section~\ref{elementary} can be modified to give the bound of Theorem~\ref{main2} for difference sets. We do not see how one can do this for the sumsets.

\section*{Acknowledgements}

The first author is partially supported by NSF grant  DMS--1501982 and would
like to thank Kevin Ford for financial support. This work was completed while the first author enjoyed the hospitality of JKU Linz and was partially supported by the Austrian Science Fund, Project F5507--N26, which is part of the Special Research Program, ``Quasi--Monte Carlo Methods: Theory and Applications." The first author also thanks the participants of the Georgia Discrete analysis conference as well as the NSF--CBMS Conference on Additive Combinatorics from a Geometric Viewpoint for enlightening discussions. The authors are particularly grateful to Sophie Stevens. The authors also thank Oliver Roche--Newton and Audie Warren for clarifying discussions.

config: arxiv


TITLE: How many natural numbers less than 200 will have 12 factors/divisors?
QUESTION [7 upvotes]: How many natural numbers less than 200 will have 12 factors (a.k.a. divisors)?

I think the answer is $11$.
Firstly there can be at most $3$ distinct prime factors.
$12=1\cdot12
  =2\cdot6
  =3\cdot4
  =2\cdot2\cdot3$
$N=a^{11}
 =a\cdot b^5
 =a^2\cdot b^3
 =a\cdot b\cdot c^2$
Then, $1$ prime factor is not possible because the smallest $2^{11}> 200$. So, the options are:
For $2$ prime factors:
$72, 96, 160$
For $3$ prime factors:
$60,90,150,84,140,126,132,156$.
I think this list is exhaustive. But am I right? Is there any other approach?

REPLY [6 votes]: I know you guys love your maths (and I do too) but, for something as finite as this (i.e., not something that would consume years of compute time), you can test it with an exhaustive computer program, one that takes about three thousandths of a second on my desktop:
#include <stdio.h>

int main (int argc, char *argv[]) {
    int quantN[200] = {0};

    for (int number = 1; number < 200; number++) {
        int quant = 0;

        for (int divisor = 1; divisor <= number; divisor++)
            if (number % divisor == 0)
                quant++;

        printf ("%3d: (%2d):", number, quant);
        quantN[quant]++;

        for (int divisor = 1; divisor <= number; divisor++)
            if (number % divisor == 0)
                printf (" %3d", divisor);

        putchar ('\n');
    }

    putchar ('\n');
    for (int quant = 0; quant < 200; quant++)
        if (quantN[quant] > 0)
            printf ("Quantity with %2d factors is %d\n",
                quant, quantN[quant]);

    return 0;
}

The relevant lines of that output are:
 60: (12):   1   2   3   4   5   6  10  12  15  20  30  60
 72: (12):   1   2   3   4   6   8   9  12  18  24  36  72
 84: (12):   1   2   3   4   6   7  12  14  21  28  42  84
 90: (12):   1   2   3   5   6   9  10  15  18  30  45  90
 96: (12):   1   2   3   4   6   8  12  16  24  32  48  96
108: (12):   1   2   3   4   6   9  12  18  27  36  54 108
126: (12):   1   2   3   6   7   9  14  18  21  42  63 126
132: (12):   1   2   3   4   6  11  12  22  33  44  66 132
140: (12):   1   2   4   5   7  10  14  20  28  35  70 140
150: (12):   1   2   3   5   6  10  15  25  30  50  75 150
156: (12):   1   2   3   4   6  12  13  26  39  52  78 156
160: (12):   1   2   4   5   8  10  16  20  32  40  80 160
198: (12):   1   2   3   6   9  11  18  22  33  66  99 198

Quantity with 12 factors is 13

The complete output of that is shown below, and I'll ask in advance for forgiveness for butchering the English language with the phrase "Quantity with 1 factors is 1" but I don't see the need for making the program grammatically aware for what is, in essence, a one-off activity.
Or you can just take that to mean I'm basically lazy :-)
  1: ( 1):   1
  2: ( 2):   1   2
  3: ( 2):   1   3
  4: ( 3):   1   2   4
  5: ( 2):   1   5
  6: ( 4):   1   2   3   6
  7: ( 2):   1   7
  8: ( 4):   1   2   4   8
  9: ( 3):   1   3   9
 10: ( 4):   1   2   5  10
 11: ( 2):   1  11
 12: ( 6):   1   2   3   4   6  12
 13: ( 2):   1  13
 14: ( 4):   1   2   7  14
 15: ( 4):   1   3   5  15
 16: ( 5):   1   2   4   8  16
 17: ( 2):   1  17
 18: ( 6):   1   2   3   6   9  18
 19: ( 2):   1  19
 20: ( 6):   1   2   4   5  10  20
 21: ( 4):   1   3   7  21
 22: ( 4):   1   2  11  22
 23: ( 2):   1  23
 24: ( 8):   1   2   3   4   6   8  12  24
 25: ( 3):   1   5  25
 26: ( 4):   1   2  13  26
 27: ( 4):   1   3   9  27
 28: ( 6):   1   2   4   7  14  28
 29: ( 2):   1  29
 30: ( 8):   1   2   3   5   6  10  15  30
 31: ( 2):   1  31
 32: ( 6):   1   2   4   8  16  32
 33: ( 4):   1   3  11  33
 34: ( 4):   1   2  17  34
 35: ( 4):   1   5   7  35
 36: ( 9):   1   2   3   4   6   9  12  18  36
 37: ( 2):   1  37
 38: ( 4):   1   2  19  38
 39: ( 4):   1   3  13  39
 40: ( 8):   1   2   4   5   8  10  20  40
 41: ( 2):   1  41
 42: ( 8):   1   2   3   6   7  14  21  42
 43: ( 2):   1  43
 44: ( 6):   1   2   4  11  22  44
 45: ( 6):   1   3   5   9  15  45
 46: ( 4):   1   2  23  46
 47: ( 2):   1  47
 48: (10):   1   2   3   4   6   8  12  16  24  48
 49: ( 3):   1   7  49
 50: ( 6):   1   2   5  10  25  50
 51: ( 4):   1   3  17  51
 52: ( 6):   1   2   4  13  26  52
 53: ( 2):   1  53
 54: ( 8):   1   2   3   6   9  18  27  54
 55: ( 4):   1   5  11  55
 56: ( 8):   1   2   4   7   8  14  28  56
 57: ( 4):   1   3  19  57
 58: ( 4):   1   2  29  58
 59: ( 2):   1  59
 60: (12):   1   2   3   4   5   6  10  12  15  20  30  60
 61: ( 2):   1  61
 62: ( 4):   1   2  31  62
 63: ( 6):   1   3   7   9  21  63
 64: ( 7):   1   2   4   8  16  32  64
 65: ( 4):   1   5  13  65
 66: ( 8):   1   2   3   6  11  22  33  66
 67: ( 2):   1  67
 68: ( 6):   1   2   4  17  34  68
 69: ( 4):   1   3  23  69
 70: ( 8):   1   2   5   7  10  14  35  70
 71: ( 2):   1  71
 72: (12):   1   2   3   4   6   8   9  12  18  24  36  72
 73: ( 2):   1  73
 74: ( 4):   1   2  37  74
 75: ( 6):   1   3   5  15  25  75
 76: ( 6):   1   2   4  19  38  76
 77: ( 4):   1   7  11  77
 78: ( 8):   1   2   3   6  13  26  39  78
 79: ( 2):   1  79
 80: (10):   1   2   4   5   8  10  16  20  40  80
 81: ( 5):   1   3   9  27  81
 82: ( 4):   1   2  41  82
 83: ( 2):   1  83
 84: (12):   1   2   3   4   6   7  12  14  21  28  42  84
 85: ( 4):   1   5  17  85
 86: ( 4):   1   2  43  86
 87: ( 4):   1   3  29  87
 88: ( 8):   1   2   4   8  11  22  44  88
 89: ( 2):   1  89
 90: (12):   1   2   3   5   6   9  10  15  18  30  45  90
 91: ( 4):   1   7  13  91
 92: ( 6):   1   2   4  23  46  92
 93: ( 4):   1   3  31  93
 94: ( 4):   1   2  47  94
 95: ( 4):   1   5  19  95
 96: (12):   1   2   3   4   6   8  12  16  24  32  48  96
 97: ( 2):   1  97
 98: ( 6):   1   2   7  14  49  98
 99: ( 6):   1   3   9  11  33  99
100: ( 9):   1   2   4   5  10  20  25  50 100
101: ( 2):   1 101
102: ( 8):   1   2   3   6  17  34  51 102
103: ( 2):   1 103
104: ( 8):   1   2   4   8  13  26  52 104
105: ( 8):   1   3   5   7  15  21  35 105
106: ( 4):   1   2  53 106
107: ( 2):   1 107
108: (12):   1   2   3   4   6   9  12  18  27  36  54 108
109: ( 2):   1 109
110: ( 8):   1   2   5  10  11  22  55 110
111: ( 4):   1   3  37 111
112: (10):   1   2   4   7   8  14  16  28  56 112
113: ( 2):   1 113
114: ( 8):   1   2   3   6  19  38  57 114
115: ( 4):   1   5  23 115
116: ( 6):   1   2   4  29  58 116
117: ( 6):   1   3   9  13  39 117
118: ( 4):   1   2  59 118
119: ( 4):   1   7  17 119
120: (16):   1   2   3   4   5   6   8  10  12  15  20  24  30  40  60 120
121: ( 3):   1  11 121
122: ( 4):   1   2  61 122
123: ( 4):   1   3  41 123
124: ( 6):   1   2   4  31  62 124
125: ( 4):   1   5  25 125
126: (12):   1   2   3   6   7   9  14  18  21  42  63 126
127: ( 2):   1 127
128: ( 8):   1   2   4   8  16  32  64 128
129: ( 4):   1   3  43 129
130: ( 8):   1   2   5  10  13  26  65 130
131: ( 2):   1 131
132: (12):   1   2   3   4   6  11  12  22  33  44  66 132
133: ( 4):   1   7  19 133
134: ( 4):   1   2  67 134
135: ( 8):   1   3   5   9  15  27  45 135
136: ( 8):   1   2   4   8  17  34  68 136
137: ( 2):   1 137
138: ( 8):   1   2   3   6  23  46  69 138
139: ( 2):   1 139
140: (12):   1   2   4   5   7  10  14  20  28  35  70 140
141: ( 4):   1   3  47 141
142: ( 4):   1   2  71 142
143: ( 4):   1  11  13 143
144: (15):   1   2   3   4   6   8   9  12  16  18  24  36  48  72 144
145: ( 4):   1   5  29 145
146: ( 4):   1   2  73 146
147: ( 6):   1   3   7  21  49 147
148: ( 6):   1   2   4  37  74 148
149: ( 2):   1 149
150: (12):   1   2   3   5   6  10  15  25  30  50  75 150
151: ( 2):   1 151
152: ( 8):   1   2   4   8  19  38  76 152
153: ( 6):   1   3   9  17  51 153
154: ( 8):   1   2   7  11  14  22  77 154
155: ( 4):   1   5  31 155
156: (12):   1   2   3   4   6  12  13  26  39  52  78 156
157: ( 2):   1 157
158: ( 4):   1   2  79 158
159: ( 4):   1   3  53 159
160: (12):   1   2   4   5   8  10  16  20  32  40  80 160
161: ( 4):   1   7  23 161
162: (10):   1   2   3   6   9  18  27  54  81 162
163: ( 2):   1 163
164: ( 6):   1   2   4  41  82 164
165: ( 8):   1   3   5  11  15  33  55 165
166: ( 4):   1   2  83 166
167: ( 2):   1 167
168: (16):   1   2   3   4   6   7   8  12  14  21  24  28  42  56  84 168
169: ( 3):   1  13 169
170: ( 8):   1   2   5  10  17  34  85 170
171: ( 6):   1   3   9  19  57 171
172: ( 6):   1   2   4  43  86 172
173: ( 2):   1 173
174: ( 8):   1   2   3   6  29  58  87 174
175: ( 6):   1   5   7  25  35 175
176: (10):   1   2   4   8  11  16  22  44  88 176
177: ( 4):   1   3  59 177
178: ( 4):   1   2  89 178
179: ( 2):   1 179
180: (18):   1   2   3   4   5   6   9  10  12  15  18  20  30  36  45  60  90 180
181: ( 2):   1 181
182: ( 8):   1   2   7  13  14  26  91 182
183: ( 4):   1   3  61 183
184: ( 8):   1   2   4   8  23  46  92 184
185: ( 4):   1   5  37 185
186: ( 8):   1   2   3   6  31  62  93 186
187: ( 4):   1  11  17 187
188: ( 6):   1   2   4  47  94 188
189: ( 8):   1   3   7   9  21  27  63 189
190: ( 8):   1   2   5  10  19  38  95 190
191: ( 2):   1 191
192: (14):   1   2   3   4   6   8  12  16  24  32  48  64  96 192
193: ( 2):   1 193
194: ( 4):   1   2  97 194
195: ( 8):   1   3   5  13  15  39  65 195
196: ( 9):   1   2   4   7  14  28  49  98 196
197: ( 2):   1 197
198: (12):   1   2   3   6   9  11  18  22  33  66  99 198
199: ( 2):   1 199

Quantity with  1 factors is 1
Quantity with  2 factors is 46
Quantity with  3 factors is 6
Quantity with  4 factors is 59
Quantity with  5 factors is 2
Quantity with  6 factors is 27
Quantity with  7 factors is 1
Quantity with  8 factors is 31
Quantity with  9 factors is 3
Quantity with 10 factors is 5
Quantity with 12 factors is 13
Quantity with 14 factors is 1
Quantity with 15 factors is 1
Quantity with 16 factors is 2
Quantity with 18 factors is 1


TITLE: A Proof Involving an Increasing Chain of Ideals in a C$^{*}$-Algebra in Davidson's Book
QUESTION [2 upvotes]: I am having trouble understanding how the following underlined passage follows:

Background: This is from the proof concerning the correspondence of ideals in AF-algebras with directed hereditary sets of the Bratteli diagrams at the top of page 86 of Davidson's C$^{*}$-algebras book.
Basically: (all ideals are closed two-sided ideals)
$\mathfrak{U}$ is an AF-algebra: $\mathfrak{U}=\overline{\bigcup_{p=1}^{\infty}\mathfrak{U_{p}}}$, where the $\mathfrak{U_{p}}$ are an increasing sequence of finite dimensional C$^{*}$-algebras. $\mathfrak{J_{p}}$ is an ideal in $\mathfrak{U_{p}}$, $\mathfrak{J_{1}}\subset\mathfrak{J_{2}}\subset\cdots$,  and $\mathfrak{J}=\overline{\bigcup_{p=1}^{\infty}\mathfrak{J_{p}}}$ is an ideal in $\mathfrak{U}$. We know that $\mathfrak{J_{p}}=\mathfrak{U_{p}}\cap \mathfrak{J_{p+1}}$.
I am having trouble understanding how we can use this to conclude that $\mathfrak{J_{p}}=\mathfrak{U_{p}}\cap\mathfrak{J}$.
For $j\geq p$, we can deduce that
$$
\mathfrak{J_{p}}=\mathfrak{U_{p}}\cap \mathfrak{J_{p+1}}
=\mathfrak{U}_{p}\cap\mathfrak{U_{p+1}}\cap\mathfrak{J_{p+2}}=\cdots=\mathfrak{U_{p}}\cap\cdots\cap\mathfrak{U_{j-1}}\cap\mathfrak{J_{j}}=\mathfrak{U_{p}}\cap\mathfrak{J_{j}},
$$
from which we can conclude that
$$
\mathfrak{U_{p}}\cap\bigcup_{j\geq p}\mathfrak{J_{j}}=\mathfrak{J_{p}}.
$$
However, I don't know how to obtain that
$$
\mathfrak{U_{p}}\cap\overline{\bigcup_{j\geq p}\mathfrak{J_{j}}}=\mathfrak{J_{p}},
$$
which is what the text claims.
Any help would really be appreciated.
Thank you.

REPLY [1 votes]: You can use the fact that $U_p\cap J = U_pJ$, the linear span of elements of the form $xy$ where $x\in U_p$ and $y\in J$. You have already shown that $J_p\subset U_p\cap J$, so it suffices to show the reverse inclusion. Hence, it suffices to show that if $x\in U_p, y\in J$, then $xy\in J_p$.
For $\epsilon > 0, \exists z\in J_j$ for $j$ large enough such that $\|y-z\| < \epsilon/\|x\|$, so that $\|xy-xz\| < \epsilon$. By what you have shown, $xz\in U_p\cap J_j \subset J_p$, so since $J_p$ is closed, $xy\in J_p$ as well.


TITLE: Implicit differentiation. Confusing assumption.
QUESTION [0 upvotes]: I've encountered this example of implicit differentiation. The problem asks us to find the derivative of $y^2 + x^2 = 4$

How can they assume that y is a function x when it clearly is not? If we isolate y, we get: $y = \pm \sqrt{4-x^2}$. So then how can we assumt that y is a function of x?
On a high level, I'm still a bit confused. So I guess implicit differentiation is useful when we have relations between y and x that aren't functions. That's why the $\frac{dy}{dx}$ is in term of 2 variables. $\frac{dy}{dx}$ has two values depending on the value of x and the value of y since at x, there are 2 values of y. Is that right?

REPLY [1 votes]: Osama Ghani has pointed out the right idea to have in mind. I'll just add a bit of detail to what he is hinting at.
We know the set of solutions to the equation
$$y^2+x^2=4$$
is simply the circle of radius 2. You are certainly correct in pointing out that the circle is not the graph of a differentiable function of $x$. However, let's not forget that the operation of differentiation is a local one -- we take the derivative at each point of a given function.
Then the crucial idea is that for each point on the circle $(x,y)\in \{(x,y)\in \mathbb{R}^2:x^2+y^2=4\}$, if we intersect a small ball (centered at $(x,y)$) of some radius $\delta$ with the circle, we do in fact get the graph of a function --
 it looks like an arc on the circle. This function depends on the chosen point and its domain is restricted according to the radius $\delta$. The observation you made is simply that these local functions are not the restrictions of a globally defined function.
Note also that the final answer for $\frac{dy}{dx}$ (when solved implicitly) depends on both $x$ and $y$ and not simply $x$. This again is because $y$ is not globally a function of $x$. You need to specify a pair $(x,y)$ to give a locally defined function $y(x)$, whose graph contains the point $(x,y)$.


text:
\begin{document}
\title{A remark on the paper \textquotedblleft A Unified Pietsch Domination
Theorem\textquotedblright}
\author{Daniel Pellegrino and Joedson Santos}
\address[D. Pellegrino]{ Departamento de Matem\'{a}tica, Universidade Federal da
Para\'{\i}ba, 58.051-900 - Jo\~{a}o Pessoa, Brazil\\
[J. Santos] Departamento de Matem\'{a}tica, Universidade Federal de Sergipe,
49500-000- Itabaiana, Brazil}
\email{dmpellegrino@gmail.com}
\thanks{D. Pellegrino by INCT-Matem\'{a}tica, PROCAD-NF Capes, CNPq Grant
620108/2008-8 (Ed. Casadinho) and CNPq Grant 301237/2009-3. }

\begin{abstract}
In this short communication we show that the Unified Pietsch Domination proved
in \cite{BPRn} remains true even if we remove two of its apparently crucial hypothesis.

\end{abstract}
\maketitle

\section{Introduction}

Let $X$, $Y$ and $E$ be (arbitrary) non-void sets, $\mathcal{H}$ be a family
of mappings from $X$ to $Y$, $G$ be a Banach space and $K$ be a compact
Hausdorff topological space. Let
\[
R\colon K\times E\times G\longrightarrow\lbrack0,\infty)~\text{and}
\mathrm{~}S\colon{\mathcal{H}}\times E\times G\longrightarrow\lbrack0,\infty)
\]
be arbitrary mappings.

A mapping $f\in\mathcal{H}$ is said to be $RS$-abstract $p$-summing if there
is a constant $C>0$ so that
\begin{equation}
\left(  \sum_{j=1}^{m}S(f,x_{j},b_{j})^{p}\right)  ^{\frac{1}{p}}\leq
C\sup_{\varphi\in K}\left(  \sum_{j=1}^{m}R\left(  \varphi,x_{j},b_{j}\right)
^{p}\right)  ^{\frac{1}{p}}, \label{33M}
\end{equation}
for all $x_{1},\ldots,x_{m}\in E,$ $b_{1},\ldots,b_{m}\in G$ and
$m\in\mathbb{N}$.

The main result of \cite{BPRn} proves that under certain assumptions on $R$
and $S$ there is a quite general Pietsch Domination-type Theorem. More
precisely $R$ and $S$ must satisfy the three properties below:

\noindent\textbf{(1)} For each $f\in\mathcal{H}$, there is a $x_{0}\in E$ such
that
\[
R(\varphi,x_{0},b)=S(f,x_{0},b)=0
\]
for every $\varphi\in K$ and $b\in G$.\newline\noindent\textbf{(2)} The
mapping
\[
R_{x,b}\colon K\longrightarrow\lbrack0,\infty)~\text{defined by}
~R_{x,b}(\varphi)=R(\varphi,x,b)
\]
is continuous for every $x\in E$ and $b\in G$.\newline\noindent\textbf{(3)}
For every $\varphi\in K,x\in E,0\leq\eta\leq1,b\in G$ and $f\in{\mathcal{H}}$,
the following inequalities hold:
\[
R\left(  \varphi,x,\eta b\right)  \leq\eta R\left(  \varphi,x,b\right)
~\text{and}\mathrm{~}\eta S(f,x,b)\leq S(f,x,\eta b).
\]

The Pietsch Domination Theorem from \cite{BPRn} reads as follows:

\begin{theorem}
\label{yn} If $R$ and $S$ satisfy \textbf{(1)}, \textbf{(2)} and \textbf{(3)}
and $0<p<\infty,$ then $f\in{\mathcal{H}}$ is $RS$-abstract $p$-summing if and
only if there is a constant $C>0$ and a Borel probability measure $\mu$ on $K$
such that
\begin{equation}
S(f,x,b)\leq C\left(  \int_{K}R\left(  \varphi,x,b\right)  ^{p}d\mu\right)
^{\frac{1}{p}}
\end{equation}
for all $x\in E$ and $b\in G.$
\end{theorem}

The aim of this note is to show that, surprisingly, the hypothesis
\textbf{(1)} and \textbf{(3)} are not necessary. So, Theorem \ref{yn} is true
for arbitrary $S$ (no hypothesis is needed) and the map $R$ just needs to
satisfy \textbf{(2)}.

\section{A recent approach to PDT}

In a recent preprint \cite{joed} we have extended the Pietsch Domination
Theorem from \cite{BPRn} to a more abstract setting, which allows to deal with
more general nonlinear mappings in the cartesian product of Banach spaces. In
the present note we shall recall the argument used in \cite{joed} and a
combination of this argument with an interesting argument due to M. Mendel and
G. Schechtman (used in \cite{BPRn}) will help us to show that Theorem \ref{yn}
is valid without the hypothesis \textbf{(1)} and \textbf{(3)} on $R$ and $S$.

The first step is to prove Theorem \ref{yn} without the hypothesis
\textbf{(1)}. This result is proved in \cite{joed} in a more general setting.
Since the paper \cite{joed} is unpublished and we just need a very particular
case, we prefer to sketch the proof for this particular case. The proof of
this particular case is essentially Pietsch's original proof on a nonlinear disguise.

\begin{theorem}
\label{part}Suppose that $R$ and $S$ satisfy \textbf{(2)} and \textbf{(3)}. A
map $f\in{\mathcal{H}}$ is $RS$-abstract $p$-summing if and only if there is a
constant $C>0$ and a Borel probability measure $\mu$ on $K$ such that
\begin{equation}
S(f,x,b)\leq C\left(  \int_{K}R\left(  \varphi,x,b\right)  ^{p}d\mu\right)
^{1/p} \label{gupdt}
\end{equation}
for all $x\in E$ and $b\in G.$
\end{theorem}

\begin{proof}
If (\ref{gupdt}) holds it is easy to show that $f$ is $RS$-abstract
$p$-summing. For the converse, consider the (compact) set $P(K)$ of the
probability measures in $C(K)^{\ast}$ (endowed with the weak-star topology).
For each $(x_{j})_{j=1}^{m}$ in $E,$ $(b_{j})_{j=1}^{m}$ in $G$ and
$m\in\mathbb{N},$ let $g:P(K)\rightarrow\mathbb{R}$ be defined by
\[
g\left(  \mu\right)  =\sum_{j=1}^{m}\left[  S(f,x_{j},b_{j})^{p}-C^{p}\int
_{K}R\left(  \varphi,x_{j},b_{j}\right)  ^{p}d\mu\right]
\]
and $\mathcal{F}$ be the set of all such $g.$ Using \textbf{(3)}, one can
prove that the family $\mathcal{F}$ is concave and each $g\in\mathcal{F}$ is
convex and continuous. Besides, for each $g\in\mathcal{F}$ there is a measure
$\mu_{g}\in P(K)$ such that $g(\mu_{g})\leq0.$ In fact, from \textbf{(2)}
there is a $\varphi_{0}\in K$ so that
\[
\sum_{j=1}^{m}R\left(  \varphi_{0},x_{j},b_{j}\right)  ^{p}=\sup_{\varphi\in
K}\sum_{j=1}^{m}R\left(  \varphi,x_{j},b_{j}\right)  ^{p}
\]
and, considering the Dirac measure $\mu_{g}=\delta_{\varphi_{0}},$ we have
$g(\mu_{g})\leq0.$ So, Ky Fan Lemma asserts that there exists a $\overline
{\mu}\in P(K)$ so that
\[
g(\overline{\mu})\leq0
\]
for all $g\in\mathcal{F}$ and by choosing an arbitrary $g$ with $m=1$ the
proof is done.
\end{proof}

\section{The main result}

Note that if each $\lambda_{j}$ is a positive integer, by considering each
$x_{j}$ repeated $\lambda_{j}$ times in (\ref{33M}) one can easily see that
(\ref{33M}) is equivalent to
\begin{equation}
\left(  \sum_{j=1}^{m}\lambda_{j}S(f,x_{j},b_{j})^{p}\right)  ^{\frac{1}{p}
}\leq C\sup_{\varphi\in K}\left(  \sum_{j=1}^{m}\lambda_{j}R\left(
\varphi,x_{j},b_{j}\right)  ^{p}\right)  ^{\frac{1}{p}}\label{eeee}
\end{equation}
for all $x_{1},\ldots,x_{m}\in E,$ $b_{1},\ldots,b_{m}\in G,$ positive
integers $\lambda_{j\text{ }}$and $m\in\mathbb{N}$. Then it is possible to
show that (\ref{33M}) holds for positive rationals and finally extend to
positive real numbers $\lambda_{j}$ (using an argument of density)$.$ The
essence of this argument appears in \cite{BPRn, FaJo} and is credited to M.
Mendel and G. Schechtman.

Now using (\ref{eeee}) and invoking Theorem \ref{part} we can prove a Pietsch
Domination-type theorem with no hypothesis on $S$ and just supposing that $R$
satisfies \textbf{(2)}:

\begin{theorem}
\label{tu} Suppose that $S$ is arbitrary and $R$ satisfies \textbf{(2)}. A map
$f\in{\mathcal{H}}$ is $RS$-abstract $p$-summing if and only if there is a
constant $C>0$ and a Borel probability measure $\mu$ on $K$ such that
\begin{equation}
S(f,x,b)\leq C\left(  \int_{K}R\left(  \varphi,x,b\right)  ^{p}d\mu\right)
^{1/p} \label{yr}
\end{equation}
for all $x\in E$ and $b\in G$.\newline

\begin{proof}
It is clear that if $f$ satisfies (\ref{yr}) then $f\in{\mathcal{H}}$ is
$RS$-abstract $p$-summing. Conversely, if $f\in{\mathcal{H}}$ is $RS$-abstract
$p$-summing, then
\begin{equation}
\left(  \sum_{j=1}^{m}\lambda_{j}S(f,x_{j},b_{j})^{p}\right)  ^{\frac{1}{p}
}\leq C\sup_{\varphi\in K}\left(  \sum_{j=1}^{m}\lambda_{j}R\left(
\varphi,x_{j},b_{j}\right)  ^{p}\right)  ^{\frac{1}{p}}\label{bbb}
\end{equation}
for all $x_{1},\ldots,x_{m}\in E,$ $b_{1},\ldots,b_{m}\in G,$ $\lambda
_{1},...,\lambda_{m}\in\lbrack0,\infty)$ and $m\in\mathbb{N}$. Let
\[
E_{1}=E\times G\text{ \ \ and \ \ }G_{1}=\mathbb{K}
\]
and define
\[
\overline{R}\colon K\times E_{1}\times G_{1}\longrightarrow\lbrack
0,\infty)\text{ \ \ and \ \ }\overline{S}\colon{\mathcal{H}}\times E_{1}\times
G_{1}\longrightarrow\lbrack0,\infty)
\]
by
\[
\overline{R}(\varphi,(x,b),\lambda)=\left\vert \lambda\right\vert
R(\varphi,x,b)\text{ \ and \ }\overline{S}(f,(x,b),\lambda)=\left\vert
\lambda\right\vert S(f,x,b).
\]

From (\ref{bbb}) we conclude that
\[
\left(  \sum_{j=1}^{m}\overline{S}(f,(x_{j},b_{j}),\eta_{j})^{p}\right)
^{\frac{1}{p}}\leq C\sup_{\varphi\in K}\left(  \sum_{j=1}^{m}\overline
{R}\left(  \varphi,(x_{j},b_{j}),\eta_{j}\right)  ^{p}\right)  ^{\frac{1}{p}}
\]
for all $x_{1},\ldots,x_{m}\in E,$ $b_{1},\ldots,b_{m}\in G,$ $\eta
_{1},...,\eta_{m}\in\mathbb{K}$ and $m\in\mathbb{N}$.

Since $\overline{R}$ and $\overline{S}$ satisfy \textbf{(2)} and \textbf{(3)},
from Theorem \ref{part} we conclude that there is a measure $\mu$ so that
\[
\overline{S}(f,(x,b),\eta)\leq C\left(  \int_{K}\overline{R}\left(
\varphi,(x,b),\eta\right)  ^{p}d\mu\right)  ^{1/p}
\]
for all $x\in E,$ $b\in G$ and $\eta\in\mathbb{K}.$ Hence it easily follows
that, for all $x\in E$ and $b\in G,$ we have
\[
S(f,x,b)\leq C\left(  \int_{K}R(\varphi,x,b)^{p}d\mu\right)  ^{1/p}.
\]

\end{proof}
\end{theorem}

\bigskip