[proofplan] We convert the energy lower bound into a dense graph of additive pairs whose restricted sumset is small by keeping only popular sums. The graph form of the [Balog-Szemerédi-Gowers theorem](/theorems/4588) then applies directly to this dense restricted-sum graph. Its conclusion supplies a large subset of $A$ with polynomially bounded doubling, which is exactly the asserted energy-form conclusion. [/proofplan] [step:Extract a popular-sum graph from the energy hypothesis] Let $N := |A|$, and define the representation function \begin{align*} r_{A+A}: G &\to \{0,1,\dots,N\} \\ x &\mapsto |\{(a,b) \in A \times A : a+b=x\}|. \end{align*} For every $x \in G$, the value $r_{A+A}(x)$ is at most $N$, because after choosing $a \in A$ there is at most one $b \in A$ with $a+b=x$. Also \begin{align*} E^+(A)=\sum_{x \in G} r_{A+A}(x)^2, \end{align*} since both sides count ordered pairs of representations of the same group element. Define the popular sum set \begin{align*} P := \{x \in G : r_{A+A}(x) \ge N/(2K)\}. \end{align*} The contribution of non-popular sums is bounded by \begin{align*} \sum_{x \in G \setminus P} r_{A+A}(x)^2 &\le \frac{N}{2K}\sum_{x \in G \setminus P} r_{A+A}(x) \\ &\le \frac{N}{2K}\sum_{x \in G} r_{A+A}(x) \\ &= \frac{N^3}{2K}, \end{align*} because $\sum_{x \in G} r_{A+A}(x)=N^2$. Since $E^+(A) \ge N^3/K$, it follows that \begin{align*} \sum_{x \in P} r_{A+A}(x)^2 \ge \frac{N^3}{2K}. \end{align*} Using $r_{A+A}(x) \le N$ for $x \in P$, we obtain \begin{align*} \sum_{x \in P} r_{A+A}(x) \ge \frac{1}{N}\sum_{x \in P} r_{A+A}(x)^2 \ge \frac{N^2}{2K}. \end{align*} The definition of $P$ and the identity $\sum_x r_{A+A}(x)=N^2$ give \begin{align*} |P|\frac{N}{2K} \le \sum_{x \in P} r_{A+A}(x) \le N^2, \end{align*} so $|P| \le 2KN$. Define the graph \begin{align*} \Gamma \subset A \times A, \qquad \Gamma := \{(a,b) \in A \times A : a+b \in P\}. \end{align*} Then \begin{align*} |\Gamma|=\sum_{x \in P} r_{A+A}(x) \ge \frac{N^2}{2K}, \end{align*} and the restricted sumset \begin{align*} A +_{\Gamma} A := \{a+b : (a,b) \in \Gamma\} \end{align*} is exactly $P$, hence $|A+_{\Gamma}A| \le 2KN$. [guided] The energy lower bound says that many ordered pairs of pairs in $A \times A$ have the same sum. We first turn this statistical statement into a graph statement by discarding sums that are represented too few times. Let $N := |A|$, and define \begin{align*} r_{A+A}: G &\to \{0,1,\dots,N\} \\ x &\mapsto |\{(a,b) \in A \times A : a+b=x\}|. \end{align*} This function counts the number of ordered representations of $x$ as a sum of two elements of $A$. For each fixed $x \in G$, once $a \in A$ is chosen there is at most one $b \in A$ satisfying $a+b=x$, so $r_{A+A}(x) \le N$. The identity \begin{align*} E^+(A)=\sum_{x \in G} r_{A+A}(x)^2 \end{align*} holds because the summand $r_{A+A}(x)^2$ counts two ordered representations $x=a_1+a_2=a_3+a_4$. Define \begin{align*} P := \{x \in G : r_{A+A}(x) \ge N/(2K)\}. \end{align*} These are the sums with many representations. If $x \notin P$, then $r_{A+A}(x)<N/(2K)$, and therefore \begin{align*} \sum_{x \in G \setminus P} r_{A+A}(x)^2 &\le \frac{N}{2K}\sum_{x \in G \setminus P} r_{A+A}(x) \\ &\le \frac{N}{2K}\sum_{x \in G} r_{A+A}(x) \\ &= \frac{N^3}{2K}. \end{align*} The last equality uses $\sum_x r_{A+A}(x)=|A \times A|=N^2$. Since the total energy is at least $N^3/K$, at least half of the required energy remains on the popular sums: \begin{align*} \sum_{x \in P} r_{A+A}(x)^2 \ge \frac{N^3}{2K}. \end{align*} Because every $r_{A+A}(x)$ is at most $N$, this forces many popular edges: \begin{align*} \sum_{x \in P} r_{A+A}(x) \ge \frac{1}{N}\sum_{x \in P} r_{A+A}(x)^2 \ge \frac{N^2}{2K}. \end{align*} At the same time, each popular sum contributes at least $N/(2K)$ representations, so the total number $N^2$ of ordered pairs bounds the number of popular sums: \begin{align*} |P|\frac{N}{2K} \le \sum_{x \in P} r_{A+A}(x) \le N^2, \end{align*} and hence $|P| \le 2KN$. Now define \begin{align*} \Gamma \subset A \times A, \qquad \Gamma := \{(a,b) \in A \times A : a+b \in P\}. \end{align*} The graph $\Gamma$ records exactly those additive pairs whose sum is popular. Its number of edges is \begin{align*} |\Gamma|=\sum_{x \in P} r_{A+A}(x) \ge \frac{N^2}{2K}. \end{align*} The restricted sumset along $\Gamma$ is \begin{align*} A +_{\Gamma} A := \{a+b : (a,b) \in \Gamma\}=P, \end{align*} so it has size at most $2KN$. This is precisely the input needed for the graph form of Balog-Szemerédi-Gowers. [/guided] [/step] [step:Apply the graph Balog-Szemerédi-Gowers theorem to obtain one large set with small doubling] We invoke the graph formulation of the [Balog-Szemerédi-Gowers Theorem](/theorems/24). In the notation of that theorem, take both vertex sets to be $A$, take the graph to be $\Gamma$, and set $L:=2K$. Since $K \ge 1$, we have $L \ge 1$. The previous step verified \begin{align*} |\Gamma| \ge \frac{N^2}{L} \end{align*} and \begin{align*} |A+_{\Gamma}A| \le LN. \end{align*} Thus the theorem applies to the finite nonempty subset $A$ of the abelian group $G$ and the graph $\Gamma \subset A \times A$. Therefore there are a subset $B \subset A$ and absolute constants $c_{\mathrm{G}},C_{\mathrm{G}}>0$ such that \begin{align*} |B| \ge c_{\mathrm{G}}L^{-C_{\mathrm{G}}}N \end{align*} and \begin{align*} |B+B| \le C_{\mathrm{G}}L^{C_{\mathrm{G}}}|B|. \end{align*} Since $L=2K$, after absorbing the fixed powers of $2$ into the absolute constants, there are absolute constants $c_*,C_*>0$ such that \begin{align*} |B| \ge c_*K^{-C_*}N \end{align*} and \begin{align*} |B+B| \le C_*K^{C_*}|B|. \end{align*} [guided] We now use the graph form of Balog-Szemerédi-Gowers. The graph formulation of the [Balog-Szemerédi-Gowers Theorem](/theorems/24) applies to a finite nonempty subset of an abelian group and a dense graph of additive pairs whose restricted sumset is small. We verify its hypotheses with \begin{align*} L:=2K. \end{align*} The assumption $K \ge 1$ gives $L \ge 1$. The underlying finite nonempty set is $A$, and the graph is the subset $\Gamma \subset A \times A$ constructed from popular sums. The preceding step established the density condition \begin{align*} |\Gamma| \ge \frac{N^2}{2K}=\frac{N^2}{L} \end{align*} and the restricted-sumset condition \begin{align*} |A+_{\Gamma}A| \le 2KN=LN. \end{align*} Thus every hypothesis of the graph formulation is satisfied. The theorem gives a subset $B \subset A$ and absolute constants $c_{\mathrm{G}},C_{\mathrm{G}}>0$ such that \begin{align*} |B| \ge c_{\mathrm{G}}L^{-C_{\mathrm{G}}}N \end{align*} and \begin{align*} |B+B| \le C_{\mathrm{G}}L^{C_{\mathrm{G}}}|B|. \end{align*} This is the point of using the graph form: it converts the dense restricted-sum graph directly into one large subset with small self-sumset, so no additional mixed-sumset conversion is needed. Substituting $L=2K$ changes only absolute constants, because powers of $2$ are fixed numerical factors. Hence there exist absolute constants $c_*,C_*>0$ such that \begin{align*} |B| \ge c_*K^{-C_*}N \end{align*} and \begin{align*} |B+B| \le C_*K^{C_*}|B|. \end{align*} [/guided] [/step] [step:Choose the subset supplied by graph Balog-Szemerédi-Gowers] Set $A':=B$, where $B \subset A$ is the subset obtained in the previous step. Since $N=|A|$, the estimates from that step give \begin{align*} |A'| \ge c_*K^{-C_*}|A| \end{align*} and \begin{align*} |A'+A'| \le C_*K^{C_*}|A'|. \end{align*} These are precisely the asserted bounds $|A'| \ge K^{-O(1)}|A|$ and $|A'+A'| \le K^{O(1)}|A'|$. [guided] The previous step already produced the correct kind of object: a single subset $B \subset A$ with polynomially large size and polynomially small doubling. We therefore define \begin{align*} A':=B. \end{align*} Because $N$ was defined as $N:=|A|$, the lower bound for $B$ becomes \begin{align*} |A'|=|B| \ge c_*K^{-C_*}N=c_*K^{-C_*}|A|. \end{align*} The doubling estimate for $B$ becomes \begin{align*} |A'+A'|=|B+B| \le C_*K^{C_*}|B|=C_*K^{C_*}|A'|. \end{align*} The constants $c_*$ and $C_*$ are absolute, so these inequalities are exactly the $K^{-O(1)}$ lower bound for the size of $A'$ and the $K^{O(1)}$ upper bound for its doubling. [/guided] [/step]