# Are these two combinatorially-defined sets of integers disjoint?

Fix an integer $$n\geq 8$$. For each integer $$i\leq n/2$$, denote by $$X_i$$ the set $$X_i = \left\{ \frac{n-i+1-k}{n-i+1}\binom nk\binom{k-1}{i-1} ~\middle|~~ i\leq k\leq n-i\right\}.$$

The question:

Are the sets $$X_1$$ and $$X_2$$ disjoint?

The reason:

The product $$\frac{n-i+1-k}{n-i+1}\binom nk\binom{k-1}{i-1}$$ is the degree in the symmetric group $$S_n$$ of the irreducible character which corresponds to the partition $$(n-k,i,1^{k-i})$$ (the latter entry meaning the cell $$1$$ repeated $$k-i$$ times), and a conjecture on which I am working will substantively advance if I get the full range of values coming from $$X_1\cup X_2$$ without having to worry about whether or not I have repetition by pulling something from $$X_1$$ then something from $$X_2$$.

The bonus question:

What I really want to be true is that $$X_1$$, $$X_2$$, and $$X_3$$ are pairwise disjoint, so a proof that covers all 3 pairs simultaneously would be the gold standard, but I would not at all be surprised if each $$X_i,X_j$$ pair had something peculiar to it that required individualized effort. For instance, one reason $$n\geq 8$$ is required is that the sets $$X_2$$ and $$X_3$$ have respectively corresponding partitions $$(5,2)$$ and $$(4,3)$$ of $$n=7$$ which both yield the integer $$14$$; they are not disjoint.

Potentially relevant information:

I readily note that, in this indexing, both $$X_1$$ and $$X_2$$ have internal redundancy, i.e., if viewed as multisets, there would be multiple appearances of some integers. I'm only asking about between sets, not within a given set.

My work:

Computer runs up into the $$n=3200$$ range say they are disjoint at least that far.

• Have you checked whether the subsets interlace each other in some way? Or are the inequalities between a given element of $X_1$ and $X_2$ predictable in some other way? – darij grinberg Aug 23 '19 at 11:12
• They don't seem to interlace or predictable. – T. Amdeberhan Aug 23 '19 at 15:19

This is to offer more evidence to the "computer run" by the OP.

Note that the members can be given by $$X_1(n,k)=\binom{n-1}k \qquad \text{and} \qquad X_2(n)=\frac{(n-1-k)(k-1)}{n-1}\binom{n}k.$$

It is not hard to show that if $$p$$ is a prime and $$n=p^m$$ then $$\{(X_1(n,k) \mod n) \mod p: 1\leq k\leq n-1\}\equiv \{\pm 1 \mod p\}$$ while $$\{(X_2(n,k) \mod n) \mod p: 2\leq k\leq n-2\}\equiv \{0 \mod p\}.$$

Hence for such numbers, $$X_1$$ and $$X_2$$ are disjoint.

• Now that you have shown me my mistake and provided correct expressions for both sets, I observe symmetry in k, n-k for the second one. We can assume a common value has j greater than =k where the common value is n-1 choose j. Now show k=2 does not occur, and get that j and k must differ by less than something like (log n)^2 or smaller. Gerhard "Will Write Something Up Later" Paseman, 2019.08.25. – Gerhard Paseman Aug 25 '19 at 15:56

Note that for a fixed n, one gets the same value in X_2 for both k and n-k, so most of these values occur twice (or more) in X_2. This also is observed in X_1. So if there is a common value between the two sets, we should find a $$j$$ with $$2j \leq n-1$$ and $$k \lt j$$ so that (n-1) choose j is a value for some $$k$$ in $$X_2$$. This leads to an interesting relation between $$n,k,$$ and $$j$$ which shows very few large primes are involved.

(If a similar condition could be established for X_3, so that only $$k \leq n/2$$ need be considered, this would help with the analysis. )

Setting up the equation implied by a shared value, and using $$k +1\lt j$$ (which is justified by the above observations: the cases $$k=j$$ and $$k+1 =j$$ are easily handled separately), we can cross multiply and divide out by the common term $$n-k-1$$ to get the relation $$(k-1)n(k+1)\cdots(j) = (n-1)(n-k)(n-k-2)\cdots(n-j).$$

I will rewrite this using $$n=m+k$$ and $$j=k+d$$ where $$d \geq 2.$$ The LHS is $$m+k \cdot k-1 \cdot 1 \cdot k+1 \cdot k+2 \cdots k+d$$ And the RHS is $$m+k-1 \cdot 1 \cdot m \cdot 1 \cdot m-2 \cdots m-d.$$ I have left off parentheses and put in 1 to draw a correspondence between the two sides.

Note that if $$d=1$$, an analogous form and divisibility constraints would have $$m+k$$ dividing $$m$$, and $$d=0$$ is resolved even more simply. Note also that we have an approximate relation : $$m^d$$ is close to $$k^{d+1}$$. A more precise and messier formulation is possible, but this one should suggest that a tight numerical relationship exists given one of $$k,m,d$$.

We have more. Let $$q$$ be a factor of $$m+k-1$$. Suppose further that $$q$$ is coprime to $$k+d$$. Then $$q$$ is coprime to $$m+k$$, divides some sub product of terms on the LHS, and also divides the corresponding product of terms on the RHS. So $$q^2$$ divides both sides when it is coprime to $$k+d$$. A similar statement holds for $$q$$ dividing $$m+k$$ and coprime to $$m$$ ( and thus $$k$$ ).

One also observes from this that there can be very few large primes involved in the product: either they are in $$n-1$$ (and therefore in $$k+d$$), or they are in $$n$$ and therefore in $$k$$, or they are in neither and the same constellation of large primes occurs "inside or near the dots". Note that all primes involved in the product must be less than $$k+d+1$$, and those primes greater than d dividing $$n(n-1)$$ and not dividing $$(k+d)k$$ must occur with multiplicity 2 or greater in one of the terms.

I suspect these observations and one other (not yet observed) will lead to an impossibility proof for $$d=2$$. In any case, one can strongly restrict the search for $$n$$ and $$k$$ given a fixed $$d.$$

Gerhard "Got It By The Tail?" Paseman, 2019.08.27.