Sharp Bounds for Sets with Distinct Subset Products

For a fixed $p\in\mathcal{P}_{\text{small}}$ and $n\in[N]$, $V_{p}(n)\in[0,\log_{2}(N)]$. Since an element of $\Pi([N])$ is a product of at most $N$ elements of $[N]$, for a fixed $n\in\Pi([N])$, $V_{p}(n)\in[0,N\log_{2}(N)]$. Thus $|\mathbf{V}_{\text{small}}(\Pi([N]))|\leq$

$$\prod_{p\in\mathcal{P}_{\text{small}}}(N\log_{2}(N)+1)=\exp(|\mathcal{P}_{\text{small}}|\log(N\log_{2}(N)+1))=\exp(O(N^{1/3+o(1)})).\qed$$

For each $\mathbf{r}\in R$, let $B_{\mathbf{r}}\subseteq A_{\mathbf{r}}$ and $C_{\mathbf{r}}\subseteq A_{\mathbf{r}}$ each have size $\lfloor|A_{\mathbf{r}}|/2\rfloor$. Then

$$\prod_{\mathbf{r}\in R}\prod_{b\in B_{\mathbf{r}}}b\quad\text{and}\quad\prod_{\mathbf{r}\in R}\prod_{c\in C_{\mathbf{r}}}c$$

each have the same valuations at all large and medium primes. There are thus at most $\exp(O(N^{1/3+o(1)}))$ elements of $\Pi(A)$ of the form $\prod_{\mathbf{r}\in R}\prod_{b\in B_{\mathbf{r}}}b$. There are at least

$$\prod_{\mathbf{r}\in R}\binom{|A_{\mathbf{r}}|}{\lfloor|A_{\mathbf{r}}|/2\rfloor}\geq\prod_{\mathbf{r}\in R}(1.1)^{|A_{\mathbf{r}}|}$$

elements of this form, where we used the inequality $\binom{n}{\lfloor n/2\rfloor}\geq(1.1)^{n}$ for all $n\geq 2$. Thus

$$(1.1)^{\sum_{\mathbf{r}\in R}|A_{\mathbf{r}}|}\leq\exp(O(N^{1/3+o(1)})),$$

and taking logarithms gives the desired inequality. ∎

For each $k\in[n]$, let $\{v_{1}^{k},\dots,v_{|C_{k}|}^{k}\}$ be the set of vertices in the cycle $C_{k}$ indexed so that $\{\{v_{1}^{k},v_{2}^{k}\},\{v_{2}^{k},v_{3}^{k}\},\dots,\{v_{|C_{k}|}^{k},v_{1}^{k}\}\}=C_{k}$. Let $A_{0}^{k}$ be the subset of $A$ corresponding to the edges $\{v_{1}^{k},v_{2}^{k}\},\{v_{3}^{k},v_{4}^{k}\},\dots,\{v_{|C_{k-1}|}^{k},v_{|C_{k}|}^{k}\}$, and let $A_{1}^{k}$ be the subset of $A$ corresponding to all the other edges in $C_{k}$. Then

$$(\mathbf{V}_{\text{large}}\times\mathbf{V}_{\text{med}})\left(\prod_{a\in A_{0}^{k}}a\right)=(\mathbf{V}_{\text{large}}\times\mathbf{V}_{\text{med}})\left(\prod_{a\in A_{1}^{k}}a\right).$$

Thus, for any choice of $\mathbf{\epsilon}\in\{0,1\}^{n}$,

$$\prod_{k=1}^{n}\prod_{a\in A_{\epsilon_{k}}^{k}}a$$

has the same valuation at all large and medium primes. By Proposition 2.1, we thus have $2^{n}=\exp(O(N^{1/3+o(1)}))$, as desired. ∎

Let $C_{1},\dots,C_{n}$ be the sets of edges in a maximal collection of edge-disjoint even circuits in $G$, each with length at most $2N^{1/12}$. We then have $\sum_{k=1}^{n}|C_{k}|=O(N^{5/12+o(1)})$, so we may remove all the edges from $\bigcup_{k=1}^{n}C_{k}$ from $G$. After doing so, if there remains an even circuit of length at most $2N^{1/12}$ in $G$, this would contradict the maximality of $\{C_{1},\dots,C_{n}\}$. ∎

We will prove the contrapositive. Suppose $G$ contains two odd cycles with vertex sets $V_{1}=\{v_{1},\dots,v_{n}\}$ and $V_{2}=\{w_{1},\dots,w_{m}\}$, respectively, such that $v_{1}=w_{1}$. Supposing also that $n+m\leq 2M$, we will show that $G$ has an even circuit of length at most $2M$. Let $E_{1}=\{\{v_{1},v_{2}\},\dots,\{v_{n},v_{1}\}\}$ and $E_{2}=\{\{w_{1},w_{2}\},\dots,\{w_{m},w_{1}\}\}$ be their respective edge sets. We consider two cases.

First, assume $E_{1}\cap E_{2}=\emptyset.$ Then $\{\{v_{1},v_{2}\},\dots,\{v_{n},v_{1}\},\{w_{1},w_{2}\},\dots,\{w_{m},w_{1}\}\}$ form a circuit of length $n+m$, which is even and at most $2M$.

On the other hand, suppose $E_{1}\cap E_{2}\neq\emptyset$. Since $E_{1}\neq E_{2}$, we may assume without loss of generality that $v_{1}=w_{1}$, $\{v_{1},v_{n}\}=\{w_{1},w_{m}\}$, but $\{v_{1},v_{2}\}\neq\{w_{1},w_{2}\}$. Let $j$ be the maximal index such that for all $1\leq i\leq j-1$, $\{v_{i},v_{i+1}\}\notin E_{2}$. Let $P_{1}$ and $P_{2}$ be the edge sets from the two paths in $E_{2}$ from $v_{1}$ to $v_{j}$. Since $|P_{1}|+|P_{2}|$ is odd, we can combine one of $P_{1}$ or $P_{2}$ with the edges from $\{\{v_{1},v_{2}\},\dots,\{v_{j-1},v_{j}\}\}$ to form an even circuit of length at most $n+m\leq 2M$. ∎

For each $k\in[n]$, let $\{v_{1}^{k},\dots,v_{|C_{k}|}^{k}\}$ be the set of vertices in the cycle $C_{k}$ indexed so that $v_{1}^{k}\in\mathcal{P}_{\square}$ and $\{\{v_{1}^{k},v_{2}^{k}\},\{v_{2}^{k},v_{3}^{k}\},\dots,\{v_{|C_{k}|}^{k},v_{1}^{k}\}\}=C_{k}$. For each $k$, let $p_{k}$ be the prime corresponding to $v_{1}^{k}$, and let $a_{k}$ be the element of $A$ such that $p_{k}^{2}$ divides $a_{k}$. Note that by Proposition 3.4, the elements $a_{k}$ are distinct for distinct $k$. Let $A_{0}^{k}$ be the set of elements of $A$ corresponding to the edges $\{v_{1}^{k},v_{2}^{k}\},\{v_{3}^{k},v_{4}^{k}\},\dots,\{v_{|C_{k}|-1}^{k},v_{|C_{k}|^{k}}\}$, and let $A_{1}^{k}$ be the set of elements of $A$ corresponding to the other edges in $C_{k}$, union $\{a_{k}\}$.

Then

$$(\mathbf{V}_{\text{large}}\times\mathbf{V}_{\text{med}})\left(\prod_{a\in A_{0}^{k}}a\right)=(\mathbf{V}_{\text{large}}\times\mathbf{V}_{\text{med}})\left(\prod_{a\in A_{1}^{k}}a\right).$$

Thus, for any choice of $\mathbf{\epsilon}\in\{0,1\}^{n}$,

$$\prod_{k=1}^{n}\prod_{a\in A_{\epsilon_{k}}^{k}}a$$

has the same valuation at all large and medium primes. By Proposition 2.1, we thus have $2^{n}=\exp(O(N^{1/3+o(1)}))$, as desired. ∎

Let $C_{1},\dots,C_{n}$ be the sets of edges of all cycles of length at most $N^{1/12}$ in $G$. By Proposition 3.4, we may assume that these sets are disjoint and that they share no vertices. None of these cycles have a vertex from $\mathcal{P}_{\square}$, and no vertices in $\mathcal{P}_{\text{large}}$ are adjacent, so each $C_{k}$ contains an edge between two vertices from $\mathcal{P}_{\not\square}\cup\{1\}$. Since the vertex sets are disjoint, we thus have $2n\leq|\mathcal{P}_{\not\square}\cup\{1\}|$. We may take $E^{\prime}$ to consist of one edge from each cycle $C_{k}$. ∎

Without loss of generality, we may assume that $G$ is connected, since we may pass to a component satisfying $|V|\geq(1+c)|E|$. We can remove degree $1$ vertices and their incident edges while preserving the inequality $|V|\geq(1+c)|E|$, so we may assume without loss of generality that each vertex has degree at least 2. If $G$ contains a path of length greater than $\frac{c+1}{c}$, then we can remove all internal edges and vertices from that path while preserving the inequality $|V|\geq(1+c)|E|$, so we may assume that $G$ has no such paths.

With all these assumptions set, we fix a vertex $v_{0}\in V$ and consider a breadth-first search starting at $v_{0}$. For each $k\in\mathbb{N}$, let $V_{k}=\{v\in V:\text{ the shortest path from $v$ to $v_{0}$ has length $k$}\}$. Fix $k\in\mathbb{N}$ with $1\leq k\leq\frac{c+1}{c}(\log_{2}(n)-1)$ and let $\ell$ be the least integer greater than $k+\frac{c+1}{c}$.

If there is a $v\in v_{\ell}$ such that there are two distinct paths of length $\ell$ from $v$ to $v_{0}$, then we are done, since $v$ must thus contain a cycle of length at most $2\ell$. Otherwise, for each $v\in v_{\ell}$, let $\varphi(v_{\ell})\in V_{k}$ be the vertex from $V_{k}$ on the shortest path from $v_{\ell}$ to $v_{0}$. For each $v\in V_{k}$, we must have $|\varphi^{-1}(v)|\geq 2$, since otherwise the path from $v$ to the only element in $\varphi^{-1}(v)$ would be a path of length greater than $\frac{c+1}{c}$ consisting only of degree two vertices. We thus have $|V_{\ell}|\geq 2|V_{k}|$. Letting $m$ be the least integer greater than $\frac{c+1}{c}\log_{2}(n)$, we must thus have $|V_{m}|>2^{\log_{2}(n)}=|V|$, so there must be a $v\in V_{m}$ with at least two distinct paths from $v$ to $v_{0}$. There is thus a cycle of length at most $2m$ in $G$, as desired. ∎

Let $\mathcal{Q}\subseteq\mathcal{P}_{\text{large}}$ be the set of vertices of degree at least $2$ in $G$. Recall that no pair of vertices in $\mathcal{P}_{\text{large}}$ is connected by an edge, so if $p\in\mathcal{Q}$, then there are distinct $v_{1},v_{2}\in\mathbf{V}_{\text{med}}\cup\{1\}$ which are each connected to $p$ by an edge.

Consider the graph with vertex set $\{1\}\cup\mathcal{P}_{\text{med}}$, where $v_{1}$ is adjacent to $v_{2}$ if there is a path of length $2$ from $v_{1}$ to $v_{2}$ in $G$ with the middle vertex in $Q$. By construction, there is a surjection from the set of edges in this graph to $\mathcal{Q}$. Moreover, this graph is simple since $G$ contains no $4$-cycles.

Any cycle of length $m$ in this graph corresponds to a circuit of length $2m$ in $G$. This graph thus does not contain any cycles of length at most $N^{1/12}$. Applying Lemma 4.1 with $c=\frac{4\log_{2}(N)}{N^{1/12}}$, we thus find that the number of edges is at most $(1+O(N^{-1/12+o(1)}))(|\mathcal{P}_{\text{med}}|+1)$, so $|\mathcal{Q}|\leq(1+O(N^{-1/12+o(1)}))\pi(N^{1/2})$. ∎

Let $A\subseteq[N]$ have distinct subset products. By Corollary 2.3, we may remove $O(N^{1/3+o(1)})$ elements from $A$ to ensure that $\mathbf{V}_{\text{large}}\times\mathbf{V}_{\text{med}}$ is injective and nonzero when restricted to $A$. We may now let $G=(V,E)$ be the prime factorization graph of $A$.

By Corollary 3.3 and Lemma 3.5, we may remove $O(N^{5/12+o(1)})$ elements from $E$ to ensure that $A$ has no even circuits of length at most $2N^{1/12}$, and to ensure that $A$ has no odd cycles of length at most $N^{1/12}$ with a vertex from $\mathcal{P}_{\square}$. Then, we may apply Lemma 3.7 and remove $\frac{1}{2}|\mathcal{P}_{\not\square}|+O(1)$ edges to remove all odd cycles of length at most $N^{1/12}$ from $G$.

Let $\mathcal{Q}$ be the set of all vertices in $\mathcal{P}_{\text{large}}$ with degree at least two. We remove all vertices from $\mathcal{P}_{\text{large}}\setminus\mathcal{Q}$ and their incident edges. Let $V^{\prime}$ and $E^{\prime}$ be the remaining sets of vertices and edges after all these removals. We have

$$|V^{\prime}|\leq 1+\pi(N^{1/2})+|\mathcal{Q}|$$

and

$$|E^{\prime}|\geq|E|-(|\mathcal{P}_{\text{large}}|-|\mathcal{Q}|)-\frac{1}{2}|\mathcal{P}_{\not\square}|-O(N^{5/12+o(1)}).$$

The graph $(V^{\prime},E^{\prime})$ has no cycles of length at most $N^{1/12}$. Applying Lemma 4.1 with $c=\frac{4\log_{2}(N)}{N^{1/12}}$, we find

$$|E^{\prime}|\leq(1+O(N^{-1/12+o(1)})|V^{\prime}|.$$

This results in the inequality

$$|E|-(|\mathcal{P}_{\text{large}}|-|\mathcal{Q}|)-\frac{1}{2}|\mathcal{P}_{\not\square}|\leq(1+O(N^{-1/12+o(1)}))(\pi(N^{1/2})+|\mathcal{Q}|)+O(N^{5/12+o(1)})=$$

$$\pi(N^{1/2})+|\mathcal{Q}|+O(N^{5/12+o(1)}),$$

where we used Lemma 4.2 so that $O(N^{-1/12+o(1)})|\mathcal{Q}|=O(N^{5/12+o(1)})$.

Finally, using the equation $|A|=|E|+|\mathcal{P}_{\square}|+O(N^{1/3+o(1)})$, we find

$$|A|\leq\pi(N^{1/2})+|\mathcal{Q}|+|\mathcal{P}_{\text{large}}|-|\mathcal{Q}|+\frac{1}{2}|\mathcal{P}_{\not\square}|+|\mathcal{P}_{\square}|+O(N^{5/12+o(1)})$$

$$\leq\pi(N)+\frac{1}{2}\pi(N^{1/2})+\frac{1}{2}|\mathcal{P}_{\square}|+O(N^{5/12+o(1)}),$$

since $\mathcal{P}_{\text{large}}=\pi(N)-\pi(N^{1/2})$ and $|\mathcal{P}_{\square}|+|\mathcal{P}_{\not\square}|\leq\pi(N^{1/2})$. ∎