3
$\begingroup$

Proving the integrality of an fractions of factorials can be done through De Polignac formula for the exponent of factorials, reducing the question to an floored inequality. Some of those inequalities turn out to be very hard to proof if true at all. The first is, given $x_i \in \mathbb{R}$ and $\{x_i\} = x_i - \lfloor x_i \rfloor$:

$$\sum_{i=1}^{n}\left \lfloor n \{x_i\} \right \rfloor \geq \left \lfloor \sum_{i=1}^{n}\{x_i\} \right \rfloor$$

I was able to prove this one by arguing that if $\left \lfloor \sum_{i=1}^{n}\{x_i\} \right \rfloor = L$ than there is some $x_k \geq \frac{L}{n}$, so the left side is at least $L$. But I was unable to apply the same idea to the following inequality:

$$\sum_{i=1}^{n}\left \lfloor q_i \{x_i\} \right \rfloor \geq \left \lfloor \sum_{i=1}^{n}\{x_i\} \right \rfloor$$ Where $q_i \in \mathbb{N}$ and $\frac{1}{q_1} + \dotsm + \frac{1}{q_n} \leq 1$. Also, this generalization was proposed: $$\sum_{i=1}^{n}\left \lfloor q_i \{x_i\} \right \rfloor \geq \left \lfloor \sum_{i=1}^{n}k_i\{x_i\} \right \rfloor$$ Where $q_i, k_i \in \mathbb{N}$ and $\frac{k_1}{q_1} + \dotsm + \frac{k_n}{q_n} \leq 1$. I don't know if the last two inequalities are correct neither know how to proof if wrong or any counter-example if not. Could someone help?

$\endgroup$
0
$\begingroup$

Let $\theta_i=\{x_i\}$, so that the second inequality reads $$\sum_{i=1}^{n}\left \lfloor q_i \theta_i \right \rfloor \geq \left \lfloor \sum_{i=1}^{n}\theta_i \right \rfloor. \tag{1}$$ Also let $L$ denote the right side, as in the proof of the OP.

Now if for each $i$ we had $\theta_i<L/q_i$ then we would have $$\sum_{i=1}^n \theta_i<L \sum_{i=1}^n \frac{1}{q_i} \le L,$$

the last inequality from the assumption that the reciprocals of the $q_i$ sum to at most $1$. From this, similar in spirit to the OP's proof, we get that for at least one index $i$ we have $\theta_i \ge L/q_i$, in other words $q_i \theta_i \ge L$, implying that the term $\left \lfloor q_i \theta_i \right \rfloor \ge L$ and establishing (1).

Perhaps a similar idea would work for the final inequality.

ADDED: Yes, the third inequality has a similar proof. With the notation above it reads

$$\sum_{i=1}^{n}\left \lfloor q_i \theta_i \right \rfloor \geq \left \lfloor \sum_{i=1}^{n}k_i\theta_i \right \rfloor. \tag{2}$$ Again let $L$ denote the right side, and assume for each $i$ we had $\theta_i<L/q_i$. then we would have $$\sum_{i=1}^n k_i\theta_i<L \sum_{i=1}^n \frac{k_i}{q_i}\le L,$$ using $\sum (k_i/q_i) \le 1.$ This as before implies there is an index $i$ for which $q_i \theta_i \ge L$ to finish.

$\endgroup$
  • $\begingroup$ Thank you, that's exactly what I was looking for. $\endgroup$ – victorsouza Jul 14 '13 at 18:36
  • $\begingroup$ @victorsouza -- Yes this was a fun problem, and note the inequalities hold for any positive quantities $\theta_i$, even if some exceed $1$, and ignoring that they are fractional parts at all. $\endgroup$ – coffeemath Jul 14 '13 at 22:21
  • $\begingroup$ Yeah, I've notice that, but they raised originally as fractional parts, so I thought that it would help someway. $\endgroup$ – victorsouza Jul 15 '13 at 0:42

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.