Skip to main content
3 of 3
gave partial progress
Zach Hunter
  • 3.5k
  • 2
  • 11
  • 24

Integer partitions with same divisors

Definitions: For $\alpha < \beta \in (0,1)$, let $P(n,\alpha,\beta)$ be the set of unordered integer partitions of $n$ where each part of the partition has size between $n^\alpha$ and $n^\beta$.

We a set of partitions, $P$, we define $f(P)$ to be the smallest integer $k$ such that for any distinct partitions $x,y \in P$, there exists $1\le d \le k$ such that the number of parts in $x$ divisible by $d$ differs from the number of parts in $y$ divisible by $d$. (note that as $d$ may equal $1$, we automatically handle cases where $x,y$ have different numbers of parts)

Questions: For $\alpha,\beta$, what can we say about the magnitude of $g(n):= f(P(n,\alpha,\beta))$? It is obvious that $g(n) \le n^\beta$. Can $g$ be subpolynomial?

For $\alpha < \beta \in (0,1)$, defining $Q(n,\alpha,\beta)$ to be the set of partitions with at most $n^{1-\beta}$ parts, each having size at least $n^\alpha$, can we get an upper bound of $h(n):= f(Q(n,\alpha,\beta))$?

Alternate Statement: It might make sense to instead define $F(P)$ to be the minimum integer $k$ such that for every pair of partitions $x,y \in P$, where $x$ and $y$ have zero parts of equal length, that there exists $1\le d\le k$ such that the number of parts in $x$ divisible by $d$ differs from the number of parts in $y$ divisible by $d$. We may then define $$G(n) = \max_{1\le m\le n}\{F(P(m,\alpha,\beta))\}, H(n) = \max_{1\le m\le n} \{F(Q(m,\alpha,\beta))\} .$$At least in my mind, this makes the asymptotics clearer and may be easier to handle as $x,y$ cannot be as similar as in the definition in $f$. While care is needed to convert bounds of $G$ and $H$ into bounds for $g$ and $h$, I would be quite interested in seeing answers to this case if it's easier.

Partial Progress: According to this post, the number of $n^\alpha$-smooth numbers less than $n^\beta$ is $(1+o(1))\rho(\beta/\alpha)n$. Thus, there exists a subset $S \subset \{m \in \Bbb{N}:n^\alpha< m<n^\beta\}$ with positive density natural such that if there exists $n+1$ distinct partitions of $n$ only using parts which are elements of $S$, it follows that $g(n) \ge n^\alpha$.

I know that for a fixed subset of the naturals $S$ with positive natural density $d>0$, that the number of partitions of $n$ only using parts which are elements of $S$ is asymptotically $e^{(1+o(1))C\sqrt{dn}}$ where $C = \pi\sqrt{2/3}$. I do not know to control the asymptotics as $n$ and $S$ vary, but hopefully someone can manage to use this to show that $g(n)\ge n^\alpha$.

Zach Hunter
  • 3.5k
  • 2
  • 11
  • 24