Curious Bounds for Floor Function Sums

Thotsaporn Thanatipanonda and Elaine Wong^{1} Science Division Mahidol University International College Nakhon Pathom, 73170 Thailand

                 thotsaporn@gmail.com
                   wongey@gmail.com

Abstract

Jacobsthal was the first to study a certain kind of sum of floor functions. His work was followed by that of Carlitz, Grimson, and Tverberg. More recently, Onphaeng and Pongsriiam proved some sharp upper and lower bounds for the sums of Jacobsthal and Tverberg. In this paper, we devise concise formulas for these sums, which we then use to prove the upper and lower bounds claimed by Tverberg. Furthermore, we present conjectural lower and upper bounds for these sums.

1 Introduction

In 1957, Jacobsthal [3] defined and studied a function of the form

f_{m}(\{a_{1}, a_{2}\}, k) = ⌊\frac{a_{1} + a_{2} + k}{m} ⌋ − ⌊\frac{a_{1} + k}{m} ⌋ − ⌊\frac{a_{2} + k}{m} ⌋ + ⌊\frac{k}{m}⌋

for fixed m ∈ ℤ^{+} with a_{1}, a_{2}, k ∈ ℤ. He also defined the functions

S_{m}({a_{1}, a_{2}}, K) = ∑_{k=0}^{K} f_{m}({a_{1}, a_{2}}, k), 0 ≤ a_{1}, a_{2}, K ≤ m − 1.

1Correspondence should be addressed to Elaine Wong: wongey@gmail.com .

It is important to note that we can take advantage of the m-periodicity of f_{m}, and so we restrict our a_{1}, a_{2}, and K values accordingly for the sum. Jacobsthal, and then later Carlitz [1], Grimson [2], and Tverberg [5], proved S_{m}({a_{1}, a_{2}}, K) ≥ 0. In 2012, Tverberg [5] proposed a generalized notation for these sum functions for any set A = {a_{1}, …, a_{n}} with 0 ≤ a_{1}, …, a_{n}, K ≤ m − 1 and n = |A|, that is,

S_{m}(\{a_{1}, …, a_{n}\}, K) = ∑_{k=0}^{K} ∑_{T ⊂[1,n]}(−1)^{n−|T |} ⌊\frac{k + ∑_{i∈T} a_{i}}{m} ⌋ .

He also claimed without proof the other upper and lower bounds of S_{m} for sets {a_{1}, a_{2}} and {a_{1}, a_{2}, a_{3}} (i.e., n = 2, 3). In 2017, Onphaeng and Pongsriiam [4] furnished a proof for the upper bounds when n is even and ≥ 4 and the lower bounds when n is odd and ≥ 3. In this paper, we investigate the bounds for S_{m} for all n ∈ ℤ^{+} and supply the missing proofs of Tverberg’s upper bounds. Furthermore, we conjecture all the bounds for S_{m} not previously mentioned and summarize the findings in Table 1. Authors who claimed their bounds without proof are denoted with an asterisk (*). Otherwise, a proof is given in their corresponding paper.

n  Lower Bound Lower Bound Credit Upper Bound Upper Bound Credit
1  0  Trivial  m − 1  Trivial
2  0  Jacobsthal;  _{⌊\frac{m}{2}⌋}  Tverberg*; Corollary 8

Carlitz; Grimson; Tverberg; Theorem 9

3 −2 ⌊\frac{m}{2}⌋

Tverberg*;

⌊\frac{m}{3}⌋

Tverberg*; Corollary 14 Onphaeng, Pongsriiam

4 −3 ⌊\frac{m}{3}⌋ Conjecture 17* 4 ⌊\frac{m}{2}⌋ Onphaeng,
(Conjecture)  Pongsriiam
odd −2^{n−2} ⌊\frac{m}{2}⌋ Onphaeng, (Conjectures) Conjecture 17*
(≥ 5)  Pongsriiam
even (Conjectures) Conjecture 17* 2^{n−2} ⌊\frac{m}{2}⌋ Onphaeng,
(≥ 5)  Pongsriiam

Table 1: Bounds for S_{m}({a_{1}, …, a_{n}}, K)

We discuss the case of n = 1 in this section as it sets the foundation for the main strategy that we use to prove higher cases. We begin with an explicit definition of Jacobsthal’s sum.

Definition 1. For any m ∈ ℤ and a_{1}, K ∈ ℤ^{+} ∪ {0},

S_{m}(\{a_{1}\}, K) = ∑_{k=0}^{K} (⌊\frac{a_{1} + k}{m} ⌋ − ⌊\frac{k}{m}⌋) .

The sum can be written concisely without using the summation symbol, which we show below. Note that the periodicity that existed in the n ≥ 2 case does not exist here. However, we only prove the following proposition for 0 ≤ K ≤ m − 1 because that is all that is needed for higher values of n. We let a mod m denote the minimal non-negative representative in the ℤ/m-equivalence class.

Proposition 2. For 0 ≤ K ≤ m − 1 and a_{1} ∈ ℤ^{+} ∪ {0},

S_{m}(\{a_{1}\}, K) = ⌊\frac{a_{1}}{m}⌋ (K + 1) + max(0, (a_{1} mod m) + K − m + 1).

Proof. We observe

⌊\frac{a_{1} + k}{m} ⌋ = ⌊\frac{a_{1}}{m}⌋ + ⌊\frac{k}{m}⌋ + ⌊\{\frac{a_{1}}{m}\} + \{\frac{k}{m}\}⌋ ,

where {x} = x − ⌊x⌋, the fractional part of x. This notation is distinguished from the usual set notation according to context. Furthermore, since 0 ≤ k ≤ m − 1,

⌊\{\frac{a_{1}}{m}\} + \{\frac{k}{m}\}⌋ = ⌊\frac{a_{1} mod m}{m} + \frac{k}{m}⌋ .

The result is derived as follows:

∑_{k=0}^{K} (⌊\frac{a_{1} + k}{m} ⌋ − ⌊\frac{k}{m}⌋)

= ∑_{k=0}^{K} (⌊\frac{a_{1}}{m}⌋ + ⌊\frac{k}{m}⌋ + ⌊\{\frac{a_{1}}{m}\} + \{\frac{k}{m}\}⌋ − ⌊\frac{k}{m}⌋)

= ⌊\frac{a_{1}}{m}⌋ (K + 1) + ∑_{k=0}^{K} ⌊\frac{a_{1} mod m}{m} + \frac{k}{m}⌋

= ⌊\frac{a_{1}}{m}⌋ (K + 1) + ∑_{k=0}^{m−(a_{1} mod m)−1} ⌊\frac{(a_{1} mod m) + k}{m} ⌋

+ ∑_{k=m−(a_{1} mod m)}^{K} ⌊\frac{(a_{1} mod m) + k}{m} ⌋

= ⌊\frac{a_{1}}{m}⌋ (K + 1) + ∑_{k=0}^{m−(a_{1} mod m)−1} 0 + ∑_{k=m−(a_{1} mod m)}^{K} 1

= ⌊\frac{a_{1}}{m}⌋ (K + 1) + max(0, (a_{1} mod m) + K − m + 1).

The bounds for S_{m}({a_{1}}, K) are then easily attained from Proposition 2.

Corollary 3. For 0 ≤ a_{1}, K ≤ m − 1,

0 ≤ S_{m}({a_{1}}, K) ≤ m − 1.

In particular, the maximum occurs precisely when a_{1} = K = m − 1.

Proof. The result follows from the fact that

S_{m}({a_{1}}, K) = max(0, a_{1} + K − m + 1).

In the following sections, we use similar methods to provide bounds when n > 1 for the sums S_{m}({a_{1}, …, a_{n}}, K).

2 Lower and upper bounds for n = 2

Carlitz [1], Grimson [2], Jacobsthal [3], and Tverberg [5] all proved the lower bound for n = 2, while Tverberg was first to mention the upper bound for this case. In this section, we prove the upper bound by introducing a new form for the sum just as before. We also use this form to give a new proof for its lower bound. We do this by first writing out Jacobsthal’s sum explicitly, and then making a generalization of Proposition 2.

Definition 4. For any m ∈ ℤ^{+} and any a_{1}, a_{2}, K ∈ ℤ^{+} ∪ {0},

S_{m}(\{a_{1}, a_{2}\}, K) = ∑_{k=0}^{K} (⌊\frac{a_{1} + a_{2} + k}{m} ⌋ − ⌊\frac{a_{1} + k}{m} ⌋ − ⌊\frac{a_{2} + k}{m} ⌋ + ⌊\frac{k}{m}⌋) .

We show that the sum can be written concisely without using the summation symbol, similar to Proposition 2.

Proposition 5. For 0 ≤ K ≤ m − 1, and any a_{1}, a_{2} ∈ ℤ^{+} ∪ {0},

S_{m}(\{a_{1}, a_{2}\}, K) = (⌊\frac{a_{1} + a_{2}}{m} ⌋ − ⌊\frac{a_{1}}{m}⌋ − ⌊\frac{a_{2}}{m}⌋) (K + 1)
+ max(0, ((a_{1} + a_{2}) mod m) + K − m + 1)
− max(0, (a_{1} mod m) + K − m + 1)
− max(0, (a_{2} mod m) + K − m + 1).

Proof. Rewriting the two-variable sum in Definition 4 as a series of one-variable sums,

S_{m}({a_{1}, a_{2}}, K) = S_{m}({a_{1} + a_{2}}, K) − S_{m}({a_{1}}, K) − S_{m}({a_{2}}, K),

allows us to apply Proposition 2 to each sum to get our result.

A symmetry exists in Proposition 5. We outline the pattern in the lemma below. This, along with a partial result in Theorem 7, gives us the desired upper and lower bounds in Corollary 8 and Theorem 9, respectively.

Lemma 6. (Mirrored Sums) For 0 ≤ a_{1}, a_{2} ≤ m − 1 and 0 ≤ K ≤ m − 2,

S_{m}({a_{1}, a_{2}}, K) = S_{m}({m − a_{1}, m − a_{2}}, m − 2 − K).

Proof. It is enough to show the claim for 0 ≤ a_{1} + a_{2} ≤ m. Otherwise, we have that (m − a_{1}) + (m − a_{2}) < m, in which case we can use a similar argument by substituting a_{1} with m − a_{1} and a_{2} with m − a_{2}. For the case a_{1} = a_{2} = 0, the result trivially holds by Definition 4. For the case 0 < a_{1} + a_{2} < m, Proposition 5 simplifies to

S_{m}({a_{1}, a_{2}}, K) = max(0, a_{1} + a_{2} + K − m + 1)

− max(0, a_{1} + K − m + 1) − max(0, a_{2} + K − m + 1). (1)

Furthermore, we note that m < 2m − (a_{1} + a_{2}) < 2m, which gives

S_{m}({m − a_{1}, m − a_{2}}, m − 2 − K) = m − 1 − K + max(0, m − (a_{1} + a_{2}) − K − 1)

− max(0, m − a_{1} − K − 1) − max(0, m − a_{2} − K − 1). (2)

Now consider the following equations that use the fact that

max(0, x) − max(0, −x) = x, for all x ∈ ℝ.

\begin{matrix}max & (0, a_{1} + a_{2} + K − m + 1) − max(0, −a_{1} − a_{2} − K + m − 1) \\ = a_{1} + a_{2} + K − m + 1, \end{matrix}  (3)
\begin{matrix}max & (0, m − a_{1} − K − 1) − max(0, a_{1} + K − m + 1) \\ = m − a_{1} − K − 1, \end{matrix}  (4)
\begin{matrix}max & (0, m − a_{1} − K − 1) − max(0, a_{2} + K − m + 1) \\ = m − a_{2} − K − 1. \end{matrix}  (5)

Then, (3)+(4)+(5) confirms (1) = (2). Finally, we consider a_{1} + a_{2} = m. Here, Proposition 5 gives

\begin{aligned}S_{m} & (\{a_{1}, a_{2}\}, K) \\ & = K + 1 − max(0, a_{1} + K − m + 1) − max(0, a_{2} + K − m + 1), \end{aligned}  (6)
\begin{aligned}S_{m} & (\{m − a_{1}, m − a_{2}\}, m − 2 − K) \\ & = m − (K + 1) − max(0, m − a_{1} − K − 1) − max(0, m − a_{2} − K − 1). \end{aligned}  (7)

In this case, (4)+(5) confirms (6) = (7). This concludes the proof.

We show the upper bound for half the range of K using differences.

Theorem 7. For 0 ≤ a_{1}, a_{2} ≤ m − 1 and 0 ≤ K ≤ ⌊\frac{m}{2}⌋ − 1,

S_{m}(\{a_{1}, a_{2}\}, K) ≤ ⌊\frac{m}{2}⌋ .

Proof. We show the stronger result, that for 0 ≤ K ≤ ⌊\frac{m}{2}⌋ − 1,

S_{m}({a_{1}, a_{2}}, K) ≤ K + 1.

For the case K = 0,

S_{m}(\{a_{1}, a_{2}\}, 0) = ⌊\frac{a_{1} + a_{2}}{m} ⌋ + max(0, ((a_{1} + a_{2}) mod m) − m + 1)

− max(0, a_{1} − m + 1) − max(0, a_{2} − m + 1)

= ⌊\frac{a_{1} + a_{2}}{m} ⌋ + 0 − 0 − 0

≤ 1.

For the case 1 ≤ K ≤ ⌊\frac{m}{2}⌋ − 1, it is enough to show that

Δ_{m} := S_{m}({a_{1}, a_{2}}, K) − S_{m}({a_{1} + 1, a_{2}}, K − 1) ≤ 1.

By using Proposition 5 we explicitly write out the two sums

S_{m}(\{a_{1}, a_{2}\}, K) = ⌊\frac{a_{1} + a_{2}}{m} ⌋ (K + 1)
+ max(0, ((a_{1} + a_{2}) mod m) + K − m + 1)
− max(0, a_{1} + K − m + 1)
− max(0, a_{2} + K − m + 1),
S_{m}(\{a_{1} + 1, a_{2}\}, K − 1) = ⌊\frac{a_{1} + a_{2} + 1}{m}⌋ K
+ max(0, ((a_{1} + a_{2} + 1) mod m) + K − m)
− max(0, a_{1} + K − m + 1)
− max(0, a_{2} + K − m).

We determine Δ_{m} according to the possible values of a_{1} + a_{2} and a_{2} + K − m + 1. Case 1: (a_{1} + a_{2} < m and a_{2} + K − m + 1 ≤ 0) If a_{1} + a_{2} < m − 1, then both sums are the same.

S_{m}({a_{1}, a_{2}}, K) = 0 + max(0, a_{1} + a_{2} + K − m + 1)
− max(0, a_{1} + K − m + 1) − 0,
S_{m}({a_{1} + 1, a_{2}}, K − 1) = 0 + max(0, (a_{1} + 1) + a_{2} + K − m)
− max(0, (a_{1} + 1) + K − m) − 0.

If a_{1} + a_{2} = m − 1, then both sums evaluate to K. Therefore, we get Δ_{m} = 0. Case 2: (a_{1} + a_{2} < m and a_{2} + K − m + 1 > 0) Again, we assume a_{1} + a_{2} < m − 1.

S_{m}({a_{1}, a_{2}}, K) = 0 + max(0, a_{1} + a_{2} + K − m + 1)
− max(0, a_{1} + K − m + 1) − (a_{2} + K − m + 1),
S_{m}({a_{1} + 1, a_{2}}, K − 1) = 0 + max(0, (a_{1} + 1) + a_{2} + K − m + 1)
− max(0, (a_{1} + 1) + K − m) − (a_{2} + K − m).

Therefore, Δ_{m} = S_{m}({a_{1}, a_{2}}, K) − S_{m}({a_{1} + 1, a_{2}}, K − 1) = −1. A similar argument holds for a_{1} + a_{2} = m − 1. Case 3: (a_{1} + a_{2} ≥ m and a_{2} + K − m + 1 ≤ 0)

S_{m}({a_{1}, a_{2}}, K) = (K + 1) + max(0, (a_{1} + a_{2} − m) + K − m + 1)
− max(0, a_{1} + K − m + 1) − 0,
S_{m}({a_{1} + 1, a_{2}}, K − 1) = K + max(0, (a_{1} + 1 + a_{2} − m) + K − m)
− max(0, (a_{1} + 1) + K − m) − 0.

Therefore, Δ_{m} = S_{m}({a_{1}, a_{2}}, K) − S_{m}({a_{1} + 1, a_{2}}, K − 1) = +1.

Case 4: (a_{1} + a_{2} ≥ m and a_{2} + K − m + 1 > 0) Δ_{m} = 0 using similar reasoning to Case 2 and Case 3.

We summarize the four cases for 0 < K ≤ ⌊\frac{m}{2}⌋ − 1 in the table below.

\begin{aligned}Case & a_{1} + a_{2} & a_{2} + K − m + 1 & Δ_{m} \\ 1 & < m & ≤ 0 & 0 \\ 2 & < m & > 0 & −1 \\ 3 & ≥ m & ≤ 0 & +1 \\ 4 & ≥ m & > 0 & 0 \end{aligned}

Table 2: Summary of Δ_{m} values.

This shows that −1 ≤ Δ_{m} ≤ 1. Thus, we have shown that

S_{m}(\{a_{1}, a_{2}\}, K) ≤ S_{m}(\{a_{1}, a_{2}\}, K − 1) + 1 ≤ K + 1 ≤ ⌊\frac{m}{2}⌋ ,

for all 0 ≤ K ≤ ⌊\frac{m}{2}⌋ − 1.

We apply Lemma 6 and Theorem 7 to show the upper bound for S_{m}.

Corollary 8. For 0 ≤ a_{1}, a_{2}, K ≤ m − 1,

S_{m}(\{a_{1}, a_{2}\}, K) ≤ ⌊\frac{m}{2}⌋ .

Proof. For 0 ≤ K ≤ ⌊\frac{m}{2}⌋ − 1, Theorem 7 gives the result. For ⌊\frac{m}{2}⌋ ≤ K ≤ m − 2, S_{m}({a_{1}, a_{2}}, K) = S_{m}({m − a_{1}, m − a_{2}}, m − 2 − K) by Lemma 6. From there, we apply Theorem 7 to the right hand side and get the result. Finally, for K = m − 1, it is easily seen that S_{m}({a_{1}, a_{2}}, K) = 0. This completes the proof.

The lower bound is now easy to show using Δ_{m}.

Theorem 9. For 0 ≤ a_{1}, a_{2}, K ≤ m − 1,

0 ≤ S_{m}({a_{1}, a_{2}}, K).

Proof. Without loss of generality, we assume that 0 ≤ a_{2} ≤ a_{1} ≤ m − 1. Consider 0 ≤ K ≤ ⌊\frac{m}{2}⌋ − 1. Thus, the conditions of Case 2 (i.e., a_{1} + a_{2} < m and a_{2} + K − m + 1 > 0) cannot be met because if a_{1} + a_{2} < m, then a_{2} ≤ ⌊\frac{m}{2}⌋. So, a_{2} + K − m + 1 ≤ 0. This shows that Δ_{m} ≠ −1, which means Δ_{m} = 0 or 1. This, along with S_{m}({a_{1}, a_{2}}, 0) ≥ 0, gives us the lower bound as desired. Next, we consider ⌊\frac{m}{2}⌋ ≤ K ≤ m − 2, and apply Lemma 6 to complete the argument. Lastly, S_{m}({a_{1}, a_{2}}, m − 1) = 0. We now have the complete result.

3 Upper bound for n = 3

Onphaeng and Pongsriiam [4] already proved the lower bound for this case. In this section, we follow the style of the previous sections by rewriting the sum, observing its symmetry, and using a difference to prove the upper bound. This time, we use Tverberg’s formulation to write out the sum explicitly.

Definition 10. For any m ∈ ℤ^{+} and a_{1}, a_{2}, a_{3}, K ∈ ℤ^{+} ∪ {0},

S_{m}(\{a_{1}, a_{2}, a_{3}\}, K) = ∑_{k=0}^{K} (⌊\frac{a_{1} + a_{2} + a_{3} + k}{m} ⌋

− ⌊\frac{a_{1} + a_{2} + k}{m} ⌋ − ⌊\frac{a_{2} + a_{3} + k}{m} ⌋ − ⌊\frac{a_{1} + a_{3} + k}{m} ⌋

+ ⌊\frac{a_{1} + k}{m} ⌋ + ⌊\frac{a_{2} + k}{m} ⌋ + ⌊\frac{a_{3} + k}{m} ⌋ − ⌊\frac{k}{m}⌋) .

Like before, we show that the sum can be written concisely without using the summation symbol.

Proposition 11. For 0 ≤ K ≤ m − 1 and a_{1}, a_{2}, a_{3} ∈ ℤ^{+} ∪ {0},

S_{m}(\{a_{1}, a_{2}, a_{3}\}, K) = (⌊\frac{a_{1} + a_{2} + a_{3}}{m} ⌋ − ⌊\frac{a_{1} + a_{2}}{m} ⌋ − ⌊\frac{a_{2} + a_{3}}{m} ⌋

− ⌊\frac{a_{1} + a_{3}}{m} ⌋ + ⌊\frac{a_{1}}{m}⌋ + ⌊\frac{a_{2}}{m}⌋ + ⌊\frac{a_{3}}{m}⌋) (K + 1)

+ max(0, ((a_{1} + a_{2} + a_{3}) mod m) + K − m + 1) − max(0, ((a_{1} + a_{2}) mod m) + K − m + 1) − max(0, ((a_{2} + a_{3}) mod m) + K − m + 1) − max(0, ((a_{1} + a_{3}) mod m) + K − m + 1) + max(0, (a_{1} mod m) + K − m + 1) + max(0, (a_{2} mod m) + K − m + 1) + max(0, (a_{3} mod m) + K − m + 1).

Proof. We can rewrite our three-variable sum in Definition 10 in terms of two-variable sums, that is,

S_{m}({a_{1}, a_{2}, a_{3}}, K) = S_{m}({a_{1}, a_{2} + a_{3}}, K) − S_{m}({a_{1}, a_{2}}, K) − S_{m}({a_{1}, a_{3}}, K). (8)

We then apply Proposition 5 to each sum to get our result.

A symmetry exists for S_{m}({a_{1}, a_{2}, a_{3}}, K), similar to Lemma 6.

Lemma 12. (Mirrored Sums) For 0 ≤ a_{1}, a_{2}, a_{3} ≤ m − 1 and 0 ≤ K ≤ m − 2,

S_{m}({a_{1}, a_{2}, a_{3}}, K) = S_{m}({m − a_{1}, m − a_{2}, m − a_{3}}, m − 2 − K).

Proof. As above, we rewrite the three-variable sum as a series of two-variable sums and then reason as follows:

S_{m}({a_{1}, a_{2}, a_{3}}, K)
= S_{m}({a_{1}, a_{2} + a_{3}}, K) − S_{m}({a_{1}, a_{2}}, K) − S_{m}({a_{1}, a_{3}}, K)
= S_{m}({a_{1}, (a_{2} + a_{3}) mod m}, K) − S_{m}({a_{1}, a_{2}}, K) − S_{m}({a_{1}, a_{3}}, K)
= S_{m}({m − a_{1}, m − (a_{2} + a_{3}) mod m}, m − 2 − K)
− S_{m}({m − a_{1}, m − a_{2}}, m − 2 − K) − S_{m}({m − a_{1}, m − a_{3}}, m − 2 − K)
= S_{m}({m − a_{1}, (m − a_{2}) + (m − a_{3})}, m − 2 − K)
− S_{m}({m − a_{1}, m − a_{2}}, m − 2 − K) − S_{m}({m − a_{1}, m − a_{3}}, m − 2 − K)
= S_{m}({m − a_{1}, m − a_{2}, m − a_{3}}, m − 2 − K).

The first and fifth equalities come from (8). We take advantage of the a_{i}-periodicity of the sums in the second and fourth equalities. Lastly, we apply Lemma 6 in the third equality.

Next, we show the upper bound for half the range of K using Δ_{m}.

Theorem 13. For 0 ≤ a_{1}, a_{2}, a_{3} ≤ m − 1 and 0 ≤ K ≤ ⌊\frac{m}{2}⌋ − 1,

S_{m}(\{a_{1}, a_{2}, a_{3}\}, K) ≤ ⌊\frac{m}{3}⌋ .

Proof. Without loss of generality, we assume that 0 ≤ a_{3} ≤ a_{2} ≤ a_{1} ≤ m − 1. We break down the proof into two cases of K, that is, we would like to show

S_{m}(\{a_{1}, a_{2}, a_{3}\}, K) ≤ \begin{cases}K + 1, & if 0 ≤ K ≤ ⌊\frac{m}{3}⌋ − 1 (Case A); \\ ⌊\frac{m}{3}⌋ , & if ⌊\frac{m}{3}⌋ ≤ K ≤ ⌊\frac{m}{2}⌋ − 1 (Case B). \end{cases}

As above, we define a difference of sums,

□ _{m} := S_{m}({a_{1}, a_{2}, a_{3}}, K) − S_{m}({a_{1} + 1, a_{2}, a_{3}}, K − 1),

and note that □ _{m} can be converted to Δ_{m} via (8) as follows:

□ _{m} = S_{m}({a_{1}, a_{2}, a_{3}}, K) − S_{m}({a_{1} + 1, a_{2}, a_{3}}, K − 1)
= (S_{m}({a_{1}, a_{2} + a_{3}}, K) − S_{m}({a_{1} + 1, a_{2} + a_{3}}, K − 1))
− (S_{m}({a_{1}, a_{2}}, K) − S_{m}({a_{1} + 1, a_{2}}, K − 1))
− (S_{m}({a_{1}, a_{3}}, K) − S_{m}({a_{1} + 1, a_{3}}, K − 1))
= Δ_{m}({a_{1}, a_{2} + a_{3}}, K) − Δ_{m}({a_{1}, a_{2}}, K) − Δ_{m}({a_{1}, a_{3}}, K).

Case A: From the proof of Theorem 9, we know that

Δ_{m}({a_{1}, a_{2}}, K) ≥ 0 and Δ_{m}({a_{1}, a_{3}}, K) ≥ 0.

This, coupled with the fact that Δ_{m}({a_{1}, a_{2} + a_{3}}, K) ≤ 1 (by Table 2), gives □ _{m} ≤ 1. Furthermore, with S_{m}({a_{1}, a_{2}, a_{3}}, 0) ≤ 1, we get S_{m} ≤ K + 1 as in the proof of Theorem 7.

Case B: If □ _{m} ≤ 0, then we can use Case A (i.e., S_{m} ≤ K + 1 ≤ ⌊\frac{m}{3}⌋) to show

S_{m}(\{a_{1}, a_{2}, a_{3}\}, K) ≤ S_{m}(\{a_{1} + 1, a_{2}, a_{3}\}, K − 1) ≤ ⌊\frac{m}{3}⌋ .

If □ _{m} = 1, we show S_{m} ≤ ⌊\frac{m}{3}⌋ directly. Observe that the only way to obtain □ _{m} = 1 is when

Δ_{m}({a_{1}, a_{2} + a_{3}}, K) = +1,
Δ_{m}({a_{1}, a_{2}}, K) = 0,
Δ_{m}({a_{1}, a_{3}}, K) = 0.

This arrangement is achieved when our assumed a_{1}, a_{2}, a_{3}, K also satisfies all conditions from Table 2. So, in Table 3, we organize each row according to the restrictions that must be applied. The ‘type’ refers to the logical operator on the conditions in the same row in order to achieve that particular Δ_{m} value. Keeping these conditions in mind, we bound S_{m}({a_{1}, a_{2}, a_{3}}, K) according to whether a_{2} + a_{3} < m or not.

Δ_{m}  Condition a  Type  Condition b
+1 (1a) a_{1} + (a_{2} + a_{3}) mod m ≥ m AND (1b) ((a_{2} + a_{3}) mod m) + K − m + 1 ≤ 0
0 (2a)  a_{1} + a_{2} ≥ m  XOR (2b)  a_{2} + K − m + 1 ≤ 0
0 (3a)  a_{1} + a_{3} ≥ m  XOR (3b)  a_{3} + K − m + 1 ≤ 0

Table 3: Conditions on Δ_{m} values for Case B

Case B1: a_{2} + a_{3} < m. Conditions (1a) and (1b) simplify to

m ≤ a_{1} + a_{2} + a_{3} < 2m AND a_{2} + a_{3} + K − m + 1 ≤ 0,

which therefore satisfies (2b) and (3b), implying that it also satisfies ∼ (2a) and ∼ (3a) by the XOR condition. Thus, we get

a_{1} + a_{2} < m AND a_{2} + K − m + 1 ≤ 0,
a_{1} + a_{3} < m AND a_{3} + K − m + 1 ≤ 0.

Applying these conditions to Proposition 11 results in the following formula:

S_{m}({a_{1}, a_{2}, a_{3}}, K) = K + 1 − max(0, a_{1} + a_{2} + K − m + 1)
− max(0, a_{1} + a_{3} + K − m + 1) + max(0, a_{1} + K − m + 1),

which can be broken down into the following four subcases. Case B1.1: (a_{1} + K − m + 1 > 0)

S_{m}({a_{1}, a_{2}, a_{3}}, K) = −a_{1} − a_{2} − a_{3} + m ≤ −m + m = 0.

Case B1.2: (a_{1} + K − m + 1 ≤ 0 and a_{1} + a_{3} + K − m + 1 > 0)

S_{m}({a_{1}, a_{2}, a_{3}}, K) = K + 1 − (a_{1} + a_{2} + K − m + 1) − (a_{1} + a_{3} + K − m + 1)

= (m − a_{1} − a_{2} − a_{3}) − (a_{1} + K) + (m − 1)

≤ 0 − ⌊\frac{2m}{3}⌋ + (m − 1)

≤ ⌊\frac{m}{3}⌋ ,

because a_{1} + a_{2} + a_{3} ≥ m (1a) and a_{1} ≥ a_{2} ≥ a_{3} gives a_{1} ≥ ⌊\frac{m}{3}⌋. This, along with K ≥ ⌊\frac{m}{3}⌋, gives us the second to last line. Case B1.3: (a_{1} + a_{3} + K − m + 1 ≤ 0 and a_{1} + a_{2} + K − m + 1 > 0)

S_{m}(\{a_{1}, a_{2}, a_{3}\}, K) = m − a_{1} − a_{2} ≤ ⌊\frac{m}{3}⌋ ,

because a_{1} + a_{2} ≥ ⌊\frac{2m}{3}⌋. Case B1.4: (a_{1} + a_{2} + K − m + 1 ≤ 0) This case cannot happen because a_{1} + a_{2} + a_{3} ≥ m gives that a_{1} + a_{2} ≥ ⌊\frac{2m}{3}⌋ which means a_{1} + a_{2} + K + 1 ≥ m, contradicting the condition.

We summarize these four subcases in Table 4.

Subcase a_{1} + a_{2} + K − m + 1 a_{1} + a_{3} + K − m + 1 a_{1} + K − m + 1 S_{m}
1  > 0  > 0  > 0  ≤ 0
2  > 0  > 0  ≤ 0  ≤ ⌊\frac{m}{3}⌋
3  > 0  ≤ 0  ≤ 0  ≤ ⌊\frac{m}{3}⌋
4  ≤ 0  ≤ 0  ≤ 0  N/A

Table 4: Subcases for B1

Case B2: m ≤ a_{2} + a_{3} < 2m.

Conditions (1a) and (1b) simplify to

a_{1} + a_{2} + a_{3} ≥ 2m AND a_{2} + a_{3} + K − 2m + 1 ≤ 0,

which therefore satisfies (2a) and (3a), implying that it also satisfies ∼ (2b) and ∼ (3b) by the XOR condition. Thus, we get

a_{1} + a_{2} ≥ m AND a_{2} + K − m + 1 > 0,
a_{1} + a_{3} ≥ m AND a_{3} + K − m + 1 > 0.

Applying these conditions to Proposition 11 results in the following formula:

S_{m}({a_{1}, a_{2}, a_{3}}, K) = −(K + 1) − max(0, a_{1} + a_{2} + K − 2m + 1)

− max(0, a_{1} + a_{3} + K − 2m + 1) + (a_{1} + K − m + 1)

+ (a_{2} + K − m + 1) + (a_{3} + K − m + 1),

which can be broken down into the following three subcases.

B2.1: (a_{1} + a_{2} + K − 2m + 1 > 0 and a_{1} + a_{3} + K − 2m + 1 > 0)

S_{m}({a_{1}, a_{2}, a_{3}}, K) = −(a_{1} + a_{2} + K − 2m + 1) − (a_{1} + a_{3} + K − 2m + 1)

+ (a_{1} + a_{2} + K − 2m + 1) + (a_{3} + K − m + 1)

= m − a_{1}

≤ ⌊\frac{m}{3}⌋ ,

because a_{1} + a_{2} + a_{3} ≥ m and a_{1} ≥ a_{2} ≥ a_{3} gives a_{1} ≥ ⌊\frac{2m}{3}⌋.

B2.2: (a_{1} + a_{2} + K − 2m + 1 > 0 and a_{1} + a_{3} + K − 2m + 1 ≤ 0)

S_{m}({a_{1}, a_{2}, a_{3}}, K) = (m − a_{1}) + (a_{1} + a_{3} + K − 2m + 1)

≤ m − a_{1}

≤ ⌊\frac{m}{3}⌋ .

B2.3: (a_{1} + a_{2} + K − 2m + 1 ≤ 0)

S_{m}({a_{1}, a_{2}, a_{3}}, K) = (m − a_{1}) + (a_{1} + a_{2} + K − 2m + 1)

+ (a_{1} + a_{3} + K − 2m + 1) ≤ (m − a_{1})

≤ ⌊\frac{m}{3}⌋ .

We summarize the three cases in Table 5.

\begin{aligned}Subcase & a_{1} + a_{2} + K − 2m + 1 & a_{1} + a_{3} + K − 2m + 1 & S_{m} \\ 1 & > 0 & > 0 & ≤ ⌊\frac{m}{3}⌋ \\ 2 & > 0 & ≤ 0 & ≤ ⌊\frac{m}{3}⌋ \\ 3 & ≤ 0 & ≤ 0 & ≤ ⌊\frac{m}{3}⌋ \end{aligned}

Table 5: Subcases for B2

The results from Tables 4 and 5 complete the proof of Case B. Hence, we have proven the theorem.

Lemma 12 and Theorem 13 give the main result, which we state as a corollary.

Corollary 14. For 0 ≤ a_{1}, a_{2}, a_{3}, K ≤ m − 1,

S_{m}(\{a_{1}, a_{2}, a_{3}\}, K) ≤ ⌊\frac{m}{3}⌋ .

Proof. For 0 ≤ K ≤ ⌊\frac{m}{2}⌋ − 1, Theorem 13 gives us our result. For ⌊\frac{m}{2}⌋ ≤ K ≤ m − 2, S_{m}({a_{1}, a_{2}, a_{3}}, K) = S_{m}({m−a_{1}, m−a_{2}, m−a_{3}}, m−2−K) by Lemma 12. From there, we apply Theorem 13 to the right hand side and get the result. Finally, S_{m}({a_{1}, a_{2}, a_{3}}, m−1) = 0. This completes the proof.

4 (Not so sharp) lower bound for n = 4

Given that 0 ≤ a_{1}, a_{2}, a_{3}, a_{4}, K ≤ m − 1, the pattern of the maximum and minimum values of S_{m}({a_{1}, a_{2}, a_{3}, a_{4}}, K) is less clear, as evidenced by some results of the computer program:

Maximum Values of Sums

(S_{1}, S_{2}, …) = (0, 4, 3, 8, 7, 12, 11, 16, 15, 20, 19, 24
23, 28, 27, 32, 31, 36, 35, 40, 39, 44, …).

Minimum Values of Sums

(S_{1}, S_{2}, …) = (0, 0, −3, −2, −3, −6, −5, −6, −9,
− 8, −9, −12, −11, −12, −15, −14,
− 15, −18, −17, −18, −21, −20, …).

Onphaeng and Pongsriiam [4] showed the upper bound

S_{m}(\{a_{1}, a_{2}, a_{3}, a_{4}\}, K) ≤ 4 ⌊\frac{m}{2}⌋ .

We conjecture the lower bound

−3 ⌊\frac{m}{3}⌋ ≤ S_{m}(\{a_{1}, a_{2}, a_{3}, a_{4}\}, K).

In an attempt to prove this lower bound, we found that writing a difference of sums (like Δ_{m} or □ _{m}) is not an efficient way to approach the problem. Accordingly, we use another method to obtain the following partial result.

Theorem 15. For 0 ≤ a_{1}, a_{2}, a_{3}, a_{4}, K ≤ m − 1,

−2 ⌊\frac{m}{2}⌋ − ⌊\frac{m}{3}⌋ ≤ S_{m}(\{a_{1}, a_{2}, a_{3}, a_{4}\}, K).

Proof. We can combine the following bounds from n = 2, 3, namely,

0 ≤ S_{m}({a_{1} + a_{2} + a_{3}, a_{4}}, K),
− ⌊\frac{m}{2}⌋ ≤ −S_{m}(\{a_{1} + a_{2}, a_{4}\}, K),
− ⌊\frac{m}{2}⌋ ≤ −S_{m}(\{a_{1} + a_{3}, a_{4}\}, K),
− ⌊\frac{m}{3}⌋ ≤ −S_{m}(\{a_{2}, a_{3}, a_{4}\}, K),
0 ≤ S_{m}({a_{1}, a_{4}}, K),

along with the identity

S_{m}({a_{1}, a_{2}, a_{3}, a_{4}}, K) = S_{m}({a_{1} + a_{2} + a_{3}, a_{4}}, K) − S_{m}({a_{1} + a_{2}, a_{4}}, K)

− S_{m}({a_{1} + a_{3}, a_{4}}, K) − S_{m}({a_{2}, a_{3}, a_{4}}, K) + S_{m}({a_{1}, a_{4}}, K),

to obtain the claimed result.

5 Conjectures

In order to complete the analysis on this type of floor function problem, we want to show all the upper bounds and lower bounds for any number of variables, n. Onphaeng and Pongsriiam [4] were able to show the upper bound when n is even and the lower bound when n is odd.

Theorem 16 (Onphaeng, Pongsriiam). When n is even and m is even,

S_{m} ≤ 2^{n−2} ⌊\frac{m}{2}⌋ .

When n is odd and m is even,

−2^{n−2} ⌊\frac{m}{2}⌋ ≤ S_{m}.

The bounds on both cases are obtained exactly at

A = {m/2, m/2, …, m/2}, K = m/2 − 1.

We conjecture the missing bounds, namely, the lower bounds when n is even and the upper bounds when n is odd. To make these conjectures, we wrote a Maple program to calculate the values of S_{m}(A, K) for specific m, A, and K. For each n, the sets A and K that give extreme values of S_{m} form interesting patterns, which depend on m. Once we determine such values in A and K, we can quickly compute the extreme values of S_{m}(A, K) for each n and then use the resulting data to form a holonomic ansatz. The resulting recurrence becomes a ninth order recurrence with polynomial coefficients of degree at most 2. We summarize our findings in the following conjecture. For interested readers, this Maple code can be found on Thanatipanonda’s website (www.thotsaporn.com).

Conjecture 17. Let A := {a_{1}, a_{2}, …, a_{n}} and define max/min S_{m}(A, K) to be the maximum/minimum over all choices of a_{i} and K with 0 ≤ a_{1}, a_{2}, …, a_{n}, K ≤ m − 1 and m fixed. Furthermore, we let the function S_{m} be as defined in the first section. Suppose now

M(n) := \begin{cases}max S_{m}(A, K), & n odd; \\ min S_{m}(A, K), & n even. \end{cases}

Then for n ≥ 4, we conjecture the following result in two parts.

1. n = 4k − 1, 4k or 4k + 1, where k ∈ ℤ^{+}: Under the condition that m is a multiple of 2k + 1, the values of M(n) occur exactly at

A = \{\frac{km}{2k + 1}, \frac{km}{2k + 1}, …, \frac{km}{2k + 1}\} , K = \frac{km}{2k + 1} − 1,

or A = \{\frac{(k + 1)m}{2k + 1}, \frac{(k + 1)m}{2k + 1}, …, \frac{(k + 1)m}{2k + 1}\} , K = \frac{(k + 1)m}{2k + 1} − 1.

2. n = 4k + 2, where k ∈ ℤ^{+}: Under the condition that m is a multiple of 2k + 1 and 2k + 3, the values of M(n) occur at (among other places)

A = \{\frac{km}{2k + 1}, \frac{km}{2k + 1}, …, \frac{km}{2k + 1}\} , K = \frac{km}{2k + 1} − 1,

or A = \{\frac{(k + 1)m}{2k + 1}, \frac{(k + 1)m}{2k + 1}, …, \frac{(k + 1)m}{2k + 1}\} , K = \frac{(k + 1)m}{2k + 1} − 1,
or A = \{\frac{(k + 1)m}{2k + 3}, \frac{(k + 1)m}{2k + 3}, …, \frac{(k + 1)m}{2k + 3}\} , K = \frac{(k + 1)m}{2k + 3} − 1,
or A = \{\frac{(k + 2)m}{2k + 3}, \frac{(k + 2)m}{2k + 3}, …, \frac{(k + 2)m}{2k + 3}\} , K = \frac{(k + 2)m}{2k + 3} − 1.

Moreover, M(n) can be calculated directly from a formula similar to the equations from Propositions 5 and 11, or by

M(n) = m · f(n),

where f(n) satisfies the recurrence relation

−5(n + 3)(n − 2)f(n) = 10(n^{2} + n − 8)f(n − 1) − 4(2n^{2} − 10n + 3)f(n − 2)

− 24(2n − 11)f(n − 3) − 32(2n^{2} − 10n − 1)f(n − 4) − 192(n − 1)(n − 5)f(n − 5) + 64(2n^{2} − 22n + 51)f(n − 6) + 384(2n − 13)f(n − 7) − 256(n − 3)(n − 8)f(n − 8) + 512(n − 9)(n − 8)f(n − 9)

for n ≥ 11, with the initial conditions

f(2) = 0, f(3) = 1/3, f(4) = −1, f(5) = 2, f(6) = −3, f(7) = 8, f(8) = −18, f(9) = 36, and f(10) = −65.

For convenience, we give examples of some of the bounds (and the set A for which the values of those bounds occur) produced from the conjectures above.

• Suppose n = 4, 5 and m is a multiple of 3.

Case n = 4:

−3 · ⌊\frac{m}{3}⌋ ≤ S_{m}.

Case n = 5:

S_{m} ≤ 6 · ⌊\frac{m}{3}⌋ .

For these cases, M(n) occurs at

A = {m/3, m/3, …, m/3}, K = m/3 − 1

or A = {2m/3, 2m/3, …, 2m/3}, K = 2m/3 − 1.

• Suppose n = 6.

• If m is a multiple of 3, then

−9 · ⌊\frac{m}{3}⌋ ≤ S_{m},

with the minimum at (among other places)

A = {m/3, m/3, …, m/3}, K = m/3 − 1

or A = {2m/3, 2m/3, …, 2m/3}, K = 2m/3 − 1.

• If m is a multiple of 5, then

−15 · ⌊\frac{m}{5}⌋ ≤ S_{m},

with the minimum at (among other places)

A = {2m/5, 2m/5, …, 2m/5}, K = 2m/5 − 1
or A = {3m/5, 3m/5, …, 3m/5}, K = 3m/5 − 1.

• Suppose n = 7, 8, 9 and m is a multiple of 5.

Case n = 7:

S_{m} ≤ 40 · ⌊\frac{m}{5}⌋ .

Case n = 8:

−90 · ⌊\frac{m}{5}⌋ ≤ S_{m}.

Case n = 9:

S_{m} ≤ 180 · ⌊\frac{m}{5}⌋ .

For these cases, M(n) occurs at

A = {2m/5, 2m/5, …, 2m/5}, K = 2m/5 − 1
or A = {3m/5, 3m/5, …, 3m/5}, K = 3m/5 − 1.

6 Acknowledgements

The authors would like to thank Harry Richman and an anonymous referee, for their helpful comments and suggestions to improve this manuscript.

References

[1] L. Carlitz, Some arithmetic sums connected with the greatest integer function, Math Scand. 8 (1960), 59–64.

[2] R. C. Grimson, The evaluation of a sum of Jacobsthal, Norske Vid. Selsk. Skr. Trondheim (1974), No. 4.

[3] E. Jacobsthal, Über eine zahlentheoretische Summe, Norske Vid. Selsk. Forh. Trondheim 30 (1957), 35–41.

[4] K. Onphaeng and P. Pongsriiam, Jacobsthal and Jacobsthal-Lucas numbers and sums introduced by Jacobsthal and Tverberg, J. Integer Sequences 20 (2017), Article 17.3.6.

[5] H. Tverberg, On some number-theoretic sums introduced by Jacobsthal, Acta Arith., 155 (2012), 349–351.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 05D99. Keywords: floor function, optimization, sum.

Received September 19 2017; revised versions received February 14 2018; February 16 2018; February 18 2018. Published in Journal of Integer Sequences, February 23 2018.

Return to Journal of Integer Sequences home page.