Skip to main content
1 of 3
Zach Hunter
  • 3.5k
  • 2
  • 11
  • 24

Integer partitions with same divisors

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 partions, $P$, we define $f(P)$ to be the smallest integer $k$ such that for any distinct partition $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)

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))$?

Zach Hunter
  • 3.5k
  • 2
  • 11
  • 24