1
$\begingroup$

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$.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.