8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – darij grinberg Aug 23 '19 at 11:12
  • $\begingroup$ They don't seem to interlace or predictable. $\endgroup$ – T. Amdeberhan Aug 23 '19 at 15:19
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Aug 25 '19 at 15:56
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.