2-adic valuations of certain ratios of products of factorials and applications

Shmuel Friedland^{1} and Christian Krattenthaler^{2}^{∗}

1Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago Chicago, Illinois 60607-7045, USA

                e-mail: friedlan@uic.edu

2Fakultät für Mathematik Universität Wien, Nordbergstraße 15, A-1090 Vienna, Austria

       WWW: http://www.mat.univie.ac.at/~kratt

Abstract

We prove the conjecture of Falikman–Friedland–Loewy on the parity of the degrees of projective varieties of n × n complex symmetric matrices of rank at most k. We also characterize the parity of the degrees of projective varieties of n × n complex skew symmetric matrices of rank at most 2p. We give recursive relations which determine the parity of the degrees of projective varieties of m × n complex matrices of rank at most k. In the case the degrees of these varieties are odd, we characterize the minimal dimensions of subspaces of n × n skew symmetric real matrices and of m × n real matrices containing a nonzero matrix of rank at most k. The parity questions studied here are also of combinatorial interest since they concern the parity of the number of plane partitions contained in a given box, on the one hand, and the parity of the number of symplectic tableaux of rectangular shape, on the other hand.

2000 Mathematics Subject Classification: Primary: 11A07, 15A03; Secondary: 14M12, 14P25, 15A30. Keywords: 2-adic valuations of ratio of products of factorials, parity of degrees of determinantal varieties, subspaces of real skew symmetric matrices, subspaces of real rectangular matrices, parity of number of plane partitions, parity of number of symplectic tableaux.

∗Research partially supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe,” and by the Austrian Science Foundation FWF, grant S9607-N13, in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory.”

1 Introduction

Consider the polynomial equation z^{d} +a_{1}z^{d−1} +⋯+a_{d} = 0 over the field of complex numbers ℂ. The fundamental theorem of algebra says that this polynomial system has always a nontrivial complex solution ζ. Assume that a_{1}, …, a_{d} are real valued. Clearly, this does not imply that the polynomial equation is solvable over the field of real numbers ℝ. Since the complex solutions come in complex pairs, it is well-known that a sufficient condition for an existence of a real solution ζ is that the degree d is odd. A similar situation holds in a more general setting.

Let ℙℝ^{n} and ℙ^{n} be the real and the complex projective space of dimension n, respectively. Let V ⊂ ℙℝ^{n} be an algebraic variety, such that its complexification V_{ℂ} ⊂ ℙ^{n} is irreducible and has codimension m ≥ 1. Hence B(V_{ℂ}) = V_{ℂ}, where B : ℙ^{n} → ℙ^{n} is the involution z ↦ z̄. Recall that any linear space M ⊂ ℙ^{n} of dimension m intersects V_{ℂ}. Furthermore, for a generic M, the set V_{ℂ} ∩ M consists of a finite number, d say, of points. The positive integer d is called the degree of V_{ℂ} and is denoted by deg V_{ℂ}. As in the previous simple case, it is well-known that if deg V_{ℂ} is odd then any linear space L ⊂ ℙℝ^{n} of dimension m intersects V. Indeed, for a generic L ⊂ ℙℝ^{n}, the set V_{ℂ} ∩ L_{ℂ} consists of deg V_{ℂ} points. As this set is invariant under the involution B, we deduce that there exists ζ ∈ V_{ℂ}∩ L_{ℂ} such that B(ζ) = ζ, that is, ζ ∈ ℙℝ^{n}. A continuity argument yields that V ∩ L ≠ ∅ for any L in the Graßmannian Gr (m + 1, n + 1, ℝ). We refer to this result as the odd degree theorem.

Assume now that deg V_{ℂ} is even. Then it is not difficult to find nontrivial examples where V ∩ L′ = ∅ for some L′ ∈ Gr (m + 1, n + 1, ℝ). Moreover examples can be found among determinantal varieties, such that for any integer k ∈ [0, p) there exists L′ ∈ Gr (m + k + 1, n + 1, ℝ) satisfying V ∩ L′ = ∅, while V ∩ L ≠ ∅ for any L ∈ Gr (m + p + 1, n + 1, ℝ) (see [7, §2]).

The following generalization of the odd degree theorem is proved in [7]: Assume that deg V_{ℂ} is even and let r be a positive integer. Suppose that the codimension of the variety of the singular points of V_{ℂ} in V_{ℂ} is at least 2r + 1. Suppose furthermore that for a generic M ∈ Gr (m + 2r + 1, n + 1, ℂ) the Euler characteristic of V_{ℂ} ∩ M is odd. Then V ∩ L ≠ ∅ for any L ∈ Gr (m + 2r + 1, n + 1, ℝ).

The degree of V_{ℂ} and the Euler characteristic of V_{ℂ} ∩ M can be often computed using the projectivized complex bundles and the corresponding Chern classes of their tangent bundles, see for example [13] and [7]. It turns out that the degrees of determinantal varieties (see the special cases discussed below) are quotients of products of certain binomial coefficients (see [12] and [2, Ch. II]). Binomial coefficients appear also in Stiefel–Whitney classes [19].

Let M_{m,n}(𝔽), M_{n}(𝔽), S_{n}(𝔽), A_{n}(𝔽) be the spaces of m × n matrices, n × n matrices, n × n symmetric matrices, and n × n skew (antisymmetric) matrices with entries in 𝔽 = ℝ, ℂ, respectively. Let U_{k,m,n}(𝔽), V_{k,n}(𝔽), W_{k,n}(𝔽) be the varieties of all matrices in M_{m,n}(𝔽), S_{n}(𝔽), A_{n}(𝔽) of rank k ≤ min(m, n) or less, respectively. It is known that any A ∈ A_{n}(𝔽) has an even rank, see e.g. [9, §11.4] or §5. Hence it is enough to consider W_{2p,n}(𝔽), where 1 ≤ p ≤ ⌊\frac{n}{2}⌋. Then the projectivizations ℙU_{k,m,n}, ℙV_{k,n}(𝔽), ℙW_{2p,n}(𝔽) are irreducible varieties of codimension (m−k)(n−k), \binom{n−k+1}{2}, \binom{n−2p}{2} in the projective spaces ℙM_{m,n}(𝔽), ℙS_{n}(𝔽), ℙA_{n}(𝔽), respectively. Note that ℙU_{k−1,m,n}(𝔽), ℙV_{k−1,n}(𝔽), ℙW_{2(p−1),n}(𝔽) are the varieties of the singular points of ℙU_{k,m,n}(𝔽), ℙV_{k,n}(𝔽), ℙW_{2p,n}(𝔽), respectively. For ℙU_{k,m,n}(𝔽), ℙV_{k,n}(𝔽) see for example [2, II], and for ℙW_{2p,n}(𝔽) see §5. Let d(m, n, k, 𝔽), d_{s}(n, k, 𝔽), d_{a}(n, 2p, 𝔽) be the smallest integer ℓ such that every ℓ-dimensional subspace of M_{m,n}(𝔽), S_{n}(𝔽), A_{n}(𝔽) contains a nonzero matrix whose rank is at most k, 2p, respectively. Then

d(m, n, k, ℂ) = (m − k)(n − k) + 1, d_{s}(n, k, ℂ) = \binom{n − k + 1}{2} + 1,

d_{a}(n, 2p, ℂ) = \binom{n − 2p}{2} + 1, (1.1)

and the problem is to determine d(m, n, k, ℝ), d_{s}(n, k, ℝ), d_{a}(n, 2p, ℝ). The degrees of ℙU_{k,m,n}(ℂ), ℙV_{k,n}(ℂ), ℙW_{2p,n}(ℂ) were computed by Harris and Tu in [12],

γ_{k,m,n} := deg ℙU_{k,m,n}(ℂ) = ∏_{j=0}^{n−k−1} \begin{matrix}( & {m+j \atop m−k} & ) \\ ( & {m−k+j \atop m−k} & ) \end{matrix} = ∏_{j=0}^{n−k−1} \frac{(m + j)! j!}{(k + j)! (m − k + j)!}, (1.2)

δ_{k,n} := deg ℙV_{k,n}(ℂ) = ∏_{j=0}^{n−k−1} \begin{matrix}( & {n+j \atop n−k−j} & ) \\ ( & {2j+1 \atop j} & ) \end{matrix}, ε_{2p,n} := deg ℙW_{2p,n} = \frac{δ_{2p+1,n}}{2^{n−2p−1}} . (1.3)

For the curiosity of the reader we remark that these quantities have also combinatorial interpretations. The quantity γ_{k,m,n} counts plane partitions which are contained in an (n−k)×(m−k)×k box (see [4] and §6). On the other hand, the quantity ε_{2p,n} counts symplectic tableaux (see [15]) of a rectangular shape of size n × p, and thus several other sets of combinatorial objects (see [21] and [10] for more information on these topics).

It was shown in [6] that δ_{n−q,n} is odd if

n ≡ ±q (mod 2^{⌈log_{2} 2q⌉}).  (1.4)

For values of q and n which satisfy this condition,

d_{s}(n, n − q, ℂ) = d_{s}(n, n − q, ℝ) = \binom{q + 1}{2} + 1.  (1.5)

It was furthermore shown in [6] that this equality implies the following interesting result. Assume that n ≥ q and that n satisfies (1.4), then any \binom{q+1}{2}-dimensional subspace of S_{n}(ℝ) contains a nonzero matrix with an eigenvalue of multiplicity at least q. This statement for q = 2 yields Lax’s result [16] that any 3-dimensional subspace of S_{n}(ℝ) contains a nonzero matrix with a multiple eigenvalue for n ≡ 2 (mod 4). (This result and its generalization in [8] is of importance in the study of singularities of hyperbolic systems.)

On the other hand, it was conjectured in [6] that also the converse holds, that is, that if δ_{n−q,n} is odd then (1.4) holds. In particular, for n and q which do not satisfy (1.4), we do not have a simple way to compute d_{s}(n, n − q, ℝ). One of the main purposes of this paper is to prove this conjecture, see §§3,4. Our results yield in addition that ε_{2p,n} is odd if and only if (1.4) holds with q = n − 2p, see §5. Hence for these values of p, n we have

d_{a}(n, 2p, ℂ) = d_{a}(n, 2p, ℝ) = \binom{n − 2p}{2} + 1.  (1.6)

In particular, for n ≡ 2 (mod 4) any two-dimensional subspace of real n × n skew symmetric matrices contains a nonzero singular matrix. For n and q = n − 2p which do not satisfy the condition (1.4), we do not have a simple way to compute d_{a}(n, 2p, ℝ).

We also consider the problem of characterizing the values of k, m, n for which γ_{k,m,n} is odd. This problem seems to have a rather intricate solution. We give some partial results on this problem in §6. In particular, we provide an algorithm for computing the parity of γ_{k,m,n} from the binary expansions of k, m, n directly, without having to actually compute γ_{k,m,n} (see Remark 6.2 and Proposition 6.5). As above, if γ_{k,m,n} is odd then

d(m, n, k, ℂ) = d(m, n, k, ℝ) = (m − k)(n − k) + 1.  (1.7)

See Corollary 6.8 for the corresponding geometric results which we are able to prove.

Another purpose of this paper is to estimate the 2-adic valuation of δ_{k,n}, i.e., the largest power of 2 that divides δ_{k,n}. There are two reasons for these estimations. First, we show that our methods can give good estimates for the complex behavior of the 2-adic valuation of δ_{k,n}. Second, we recall the classical results of Radon [18] and Hurwitz [14] on the maximal dimension of the spaces of n × n scaled orthogonal matrices, and the Adams result [1] on maximal number of vectors fields on the tangent bundle of n−1-dimensional sphere, which are functions of the 2-adic valuation of n. We believe that the 2-adic valuation of deg ℙV_{k,n}(ℂ) is related to a lower bound for the problem raised in Friedland–Libgober [7].

Consider the variety of n × n singular matrices in M_{n}(𝔽). Clearly the degree of this variety is n and its codimension is 1. Hence any two-dimensional complex subspace L ⊂ M_{n}(ℂ) contains a nonzero singular matrix. For n odd, any twodimensional real subspace of M_{n}(ℝ) contains a nonzero singular matrix. For n even, the situation is much more complicated. For n ∈ ℕ, let c + 4d be the 2-adic valuation of n. Thus n = (2a + 1)2^{c+4d}, where a and d are nonnegative integers and c ∈ {0, 1, 2, 3}. Then the Radon–Hurwitz number ρ(n) is defined by ρ(n) = 2^{c} + 8d. The classical results of Radon [18] and Hurwitz [14] state that ρ(n) is the maximal dimension of an n-dimensional subspace U of M_{n}(ℝ) such that each nonzero A ∈ U is an orthogonal matrix times r ∈ ℝ^{∗}. In his famous work [1], Adams gave a nonlinear version of the Radon–Hurwitz result by showing that ρ(n) − 1 is the maximal number of linearly independent vector fields on the (n − 1)-dimensional sphere in ℝ^{n}. In particular, Adams’s result implies that any (ρ(n) + 1)-dimensional subspace of M_{n}(ℝ) contains a nonzero singular matrix.

The parity of binomial coefficients plays a role in generalized Radon–Hurwitz numbers [3, Prop. I (f)]. Similarly, we believe that the answer to the following problem raised in [7] significantly depends on the 2-adic valuation of δ_{k,n}:

Problem 1.1. Assume that δ_{k,n} is even. Find an integer r ≥ 1, preferably the smallest possible, such that 2r < \binom{n−k+2}{2}−\binom{n−k+1}{2}, and such that the Euler characteristic of ℙV_{n,k}(ℂ) ∩ M is odd for a generic M ∈ Gr (\binom{n−k+1}{2} + 2r + 1, \binom{n+1}{2}, ℂ).

For the above minimal value of r, we have ℙV_{n,k}(ℝ) ∩ L ≠ ∅ for any

L ∈ Gr (\binom{n − k + 1}{2} + 2r + 1, \binom{n + 1}{2}, ℝ) .

We now briefly survey the contents of this paper. In §2 we give some auxiliary results on the 2-adic valuation of δ_{n−q,n}. In §3 we prove the conjecture from [6] characterizing the values of q and n for which δ_{n−q,n} is odd. In §4 we discuss properties of the 2-adic valuation of δ_{n−q,n} when the condition (1.4) is not satisfied. In particular, we characterize the values of q and n for which the 2-adic valuation of δ_{n−q,n} is 1, and we show that, for fixed q, the 2-adic valuations of δ_{n−q,n} have a wave-like behavior as n increases. In §5 we show that ε_{2p,n} is odd if and only if (1.4) holds with q = n − 2p. Hence for these values of n and p the equality (1.6) holds. Finally, in §6 we study the parity of the number of plane partitions contained in an a × b × c box, and thus the parity of γ_{k,m,n}. Some partial results are given, as well as the above-mentioned algorithm for computing this parity.

2 Preliminary results on the 2-adic valuation of δ_{n−q,n}

For a nonzero integer i we write ν_{2}(i) for the 2-adic valuation of i. That is i = (2j + 1)2^{ν_{2}(i)} for some j ∈ ℤ. For positive integers q and n define

θ_{q,n} := ∏_{j=0}^{q−1} \begin{matrix}( & {n+j \atop q−j} & ) \\ ( & {2j+1 \atop j} & ) \end{matrix}.  (2.1)

The reader should note that θ_{q,n} = δ_{n−q,n} (compare (1.3)). It will be convenient later to extend the definition of θ_{q,n} to all nonnegative integers q and n, that is, to allow n = 0, respectively q = 0, in (2.1) also. In particular, for q = 0 we set θ_{0,n} = 1 by interpreting the empty product as 1.

Clearly, we have θ_{q,n} = 0 for q > n. We want to study the behavior of the 2-adic valuation of θ_{q,n} for n ≥ q. The following proposition simplifies this study as it exhibits a simple relationship between the 2-adic valuation of θ_{q,n} when n − q is even and those when n−q is odd. In particular, this result allows one to concentrate on the analysis of just one case, which will be the case where n − q is even.

Proposition 2.1. Let n and q be nonnegative integers, n ≥ q + 1. Then

ν_{2}(θ_{q,n}) = ν_{2}(θ_{q+1,n}) + q − ∑_{j=0}^{q} ν_{2}(n − q + 2j).  (2.2)

In particular, if n − q is odd then ν_{2}(θ_{q,n}) = ν_{2}(θ_{q+1,n}) + q ≥ q. Hence, if n and q are both positive, and if n − q is positive and odd, then θ_{q,n} is even.

Proof. The ratio of θ_{q+1,n} and θ_{q,n} is

\frac{θ_{q+1,n}}{θ_{q,n}} = \frac{1}{\binom{2q+1}{q}} ∏_{j=0}^{q} \frac{(n + j)!}{(q + 1 − j)! (n − q − 1 + 2j)!} ∏_{j=0}^{q−1} \frac{(q − j)! (n − q + 2j)!}{(n + j)!}

= \frac{(q)! (q + 1)!}{(2q + 1)!} \frac{(n + q)!}{1! (n + q − 1)!} ∏_{j=0}^{q−1} \frac{(q − j)! (n − q + 2j)!}{(q + 1 − j)! (n − q − 1 + 2j)!}

= \frac{(q + 1)!}{2^{q}(2q + 1)!!}(n + q) ∏_{j=0}^{q−1} \frac{(n − q + 2j)}{(q + 1 − j)} = \frac{∏_{j=0}^{q}(n − q + 2j)}{2^{q} (2q + 1)!!}.

(Here (2q + 1)!! := (2q + 1) · (2q − 1) ⋯ 3 · 1.) As (2q + 1)!! is odd, we deduce (2.2). Assume that n − q is odd. Then n − q + 2j is odd for j = 0, …, q, and the last part of the proposition follows.

We now concentrate on the case where n − q is even.

Proposition 2.2. Let n and q be nonnegative integers, n ≥ q, such that the difference of n and q is even, say n − q = 2p. Then

ν_{2}(θ_{q,n}) = (n − 1 − p)p − ν_{2} (∏_{k=1}^{p} \frac{(n − k)!}{(k − 1)!}) .  (2.3)

Here again, in case that p = 0, the empty product has to be interpreted as 1. In particular, (n − 1 − p)p ≥ ν_{2} (∏_{k=1}^{p} \frac{(n−k)!}{(k−1)!}).

Proof. We prove (2.3) by a reverse induction on q. By the definition (2.1) of θ_{q,n} we have θ_{n,n} = 1. Hence ν_{2}(θ_{n,n}) = 0, which confirms (2.3) in this case.

Proposition 2.1 implies that for any positive integer k we have

ν_{2}(θ_{n−2k+1,n}) = ν_{2}(θ_{n−2k+2,n}) + n − 2k + 1.

We now use (2.2) for q = n − 2k to obtain the recursive formula

ν_{2}(θ_{n−2k,n}) = ν_{2}(θ_{n−2k+2,n}) + n − 2k + 1 + n − 2k − ∑_{j=0}^{n−2k} ν_{2}(2k + 2j)

= ν_{2}(θ_{n−2k+2,n}) + n − 2k − ∑_{j=0}^{n−2k} ν_{2}(k + j)

= ν_{2}(θ_{n−2k+2,n}) + n − 2k − ν_{2} (\frac{(n − k)!}{(k − 1)!}) .

Use this recursive relation for k = p, p − 1, …, 1 to obtain (2.3). Since ν_{2}(θ_{q,n}) ≥ 0 we obtain that the right-hand side of (2.3) is nonnegative.

Our next goal is to give an explicit expression of the 2-adic valuation of θ_{q,n} in terms of binary digit sums. More precisely, for a nonnegative integer m let s(m) denote the sum of the digits of m when written in binary notation. Then s(0) = 0, s(2m) = s(m), s(2m + 1) = 1 + s(m), and

s(2^{e} − 1 − k) = e − s(k) for any integers e ≥ 0, k ∈ [0, 2^{e} − 1].  (2.4)

The basic result which ties together the 2-adic valuation of factorials and binary digit sums is the following one due to Legendre (cf. [11, Sec. 4.4] and [17]). We bring its proof for completeness.

Proposition 2.3. Let n be a nonnegative integer. Then ν_{2}(n!) = n − s(n).

Proof. We prove the proposition by induction. Clearly ν_{2}(1) = 0 = 0 − s(0) = 1 − s(1). Assume that the proposition holds for n ≤ m − 1. Let n = m. Suppose first that m = 2l. Then ν_{2}((2l)!) = ν_{2}((2l)!!) = ν_{2}(2^{l}l!) = l + ν_{2}(l!) = l + l − s(l) = m − s(m). Assume now that m = 2l + 1. Then ν_{2}(m!) = ν_{2}((2l)!) = 2l − s(2l) = m − s(m).

In what follows we are going to make extensive use of the following lemma and particularly of its corollary.

Lemma 2.4. Let p and q be nonnegative integers, and assume that n − q = 2p. Then

ν_{2}(θ_{q,n}) = −p + ∑_{k=1}^{p} s(n − k) − ∑_{k=1}^{p} s(k − 1).  (2.5)

If p = 0, we have to interpret empty sums as 0, as before. The equation holds also for q = 0 if we interpret, as earlier, θ_{0,2p} as 1 for any p.

Proof. Combine (2.3) and Proposition 2.3.

Since the 2-adic valuation in (2.5) must always be nonnegative, we obtain the following corollary.

Corollary 2.5. For all nonnegative integers l and p, we have

∑_{j=l}^{l+p−1} s(j) ≥ p + ∑_{j=0}^{p−1} s(j) if l ≥ p,  (2.6)

and

∑_{j=l}^{l+p−1} s(j) ≥ l + ∑_{j=0}^{p−1} s(j) if l ≤ p.  (2.7)

For l = p + 1, p, there holds equality,

0 = − ∑_{j=0}^{p−1} s(j) + ∑_{j=p+1}^{2p} s(j) − p = − ∑_{j=0}^{p−1} s(j) + ∑_{j=p}^{2p−1} s(j) − p.  (2.8)

In particular,

∑_{j=l}^{l+p−1} s(j) ≥ ∑_{j=0}^{p−1} s(j),  (2.9)

and equality holds if and only if either p = 0 or l = 0.

Proof. Use (2.5) with l = n − p = p + q to deduce (2.6). Assume that 0 ≤ l ≤ p. Then by cancelling out the common terms in (2.7) we deduce that (2.7) follows from (2.6) with the roles of l and p being interchanged.

Put q = 0 in (2.5) and recall that θ_{0,n} = 1. This implies the second part of (2.8). Use the equality s(2p) = s(p) to deduce the first part of (2.8).

The inequality (2.9) follows trivially from (2.6) and (2.7).

3 Proof of the Falikman–Friedland–Loewy Conjecture

In this section, we use the results from the previous section to prove the conjecture from [6] characterizing the values of q and n for which δ_{n−q,n} = θ_{q,n} is odd. For the sake of convenience, we state the result in form of the following theorem. The “if” direction was already shown in [6]. Our proof will not only show the “only if” direction, but, in passing, it will also provide an independent proof of the “if” direction.

Theorem 3.1. For positive integers q and n, the quantity θ_{q,n} is odd if and only if n ≥ q ≥ 1 and

n ≡ ±q (mod 2^{⌈log_{2} 2q⌉}).

Proof. For n − q odd, the theorem follows from Proposition 2.1. Therefore, for the rest of the proof, let n − q be even.

We repeatedly use subsequently the following observation. Let r, t, j be nonnegative integers such that 2^{t} > j. Then s(r2^{t} + j) = s(r) + s(j). We divide the proof into the two following cases.

Case 1. n = 2n_{1}. It is enough to assume that q = 2q_{1} and n_{1} ≥ q_{1}. Write p = n_{1} − q_{1} and substitute in (2.5) to obtain

ν_{2}(θ_{q,n}) = −(n_{1} − q_{1}) − ∑_{j=0}^{n_{1}−q_{1}−1} s(j) + ∑_{j=n_{1}+q_{1}}^{2n_{1}−1} s(j).  (3.1)

We now show that the right-hand side of (3.1) is zero if and only if

n_{1} ≡ ±q_{1} (mod 2^{⌈log_{2}(2q_{1})⌉}),

which is obviously equivalent to the theorem in this case.

In Case 1 we always use the abbreviation Q = 2^{⌈log_{2} 2q_{1}⌉}. Write n_{1} = cQ+q_{1}+d, where 0 ≤ d < Q. We know that the quantity from (3.1),

− ∑_{j=0}^{n_{1}−q_{1}−1} s(j)+ ∑_{j=n_{1}+q_{1}}^{2n_{1}−1} s(j)−(n_{1}−q_{1}) = − ∑_{j=0}^{cQ+d−1} s(j)+ ∑_{j=cQ+2q_{1}+d}^{2cQ+2q_{1}+2d−1} s(j)−(cQ+d),

(3.2)

is nonnegative. We have to show that it is zero only if d = 0 or d = Q − 2q_{1}. To do so, we distinguish various subcases, depending on the size of d.

Case 1a: 2q_{1} + 2d ≤ Q. In this case, the quantity (3.2) becomes

− ∑_{r=0}^{c−1} ∑_{j=0}^{Q−1} s(rQ + j) − ∑_{j=cQ}^{cQ+d−1} s(j) + ∑_{j=cQ+2q_{1}+d}^{(c+1)Q−1} s(j)

+ ∑_{r=c+1}^{2c−1} ∑_{j=0}^{Q−1} s(rQ + j) + ∑_{j=2cQ}^{2cQ+2q_{1}+2d−1} s(j) − (cQ + d)

= −Q ∑_{r=0}^{c−1} s(r) − c ∑_{j=0}^{Q−1} s(j) − ds(c) − ∑_{j=0}^{d−1} s(j) + (Q − 2q_{1} − d)s(c) + ∑_{j=2q_{1}+d}^{Q−1} s(j)

+ Q ∑_{r=c+1}^{2c−1} s(r) + (c − 1) ∑_{j=0}^{Q−1} s(j) + (2q_{1} + 2d)s(2c) + ∑_{j=0}^{2q_{1}+2d−1} s(j) − (cQ + d)

= Q (− ∑_{r=0}^{c−1} s(r) + ∑_{r=c+1}^{2c} s(r) − c) − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d}^{2q_{1}+2d−1} s(j) − d.

Using (2.8), we see that the above expression is equal to

− ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d}^{2q_{1}+2d−1} s(j) − d.  (3.3)

By the definitions of Q and d, we have Q/2 < 2q_{1} < 2q_{1} + 2d − 1 < Q. Thus, we have

− ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d}^{2q_{1}+2d−1} s(j) − d = − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d− \frac{Q}{2}}^{2q_{1}+2d− \frac{Q}{2} −1} s(j).  (3.4)

It should be noted that, by the definitions of Q and d, we have Q/2 < 2q_{1} + d. By (2.9), the quantity on the right-hand side is zero only if the sums on the right-hand side are empty, i.e., if d = 0.

Case 1b: 2q_{1} + d ≤ Q < 2q_{1} + 2d. In this case, the quantity (3.2) becomes

− ∑_{r=0}^{c−1} ∑_{j=0}^{Q−1} s(rQ + j) − ∑_{j=cQ}^{cQ+d−1} s(j) + ∑_{j=cQ+2q_{1}+d}^{(c+1)Q−1} s(j)

+ ∑_{r=c+1}^{2c} ∑_{j=0}^{Q−1} s(rQ + j) + ∑_{j=(2c+1)Q}^{2cQ+2q_{1}+2d−1} s(j) − (cQ + d)

= −Q ∑_{r=0}^{c−1} s(r) − c ∑_{j=0}^{Q−1} s(j) − ds(c) − ∑_{j=0}^{d−1} s(j) + (Q − 2q_{1} − d)s(c) + ∑_{j=2q_{1}+d}^{Q−1} s(j)

+ Q ∑_{r=c+1}^{2c} s(r) + c ∑_{j=0}^{Q−1} s(j) + (2q_{1} + 2d − Q)s(2c) + ∑_{j=Q}^{2q_{1}+2d−1} s(j) − (cQ + d)

= Q (− ∑_{r=0}^{c−1} s(r) + ∑_{r=c+1}^{2c} s(r) − c) − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d}^{2q_{1}+2d−1} s(j) − d.

Using (2.8) again, we deduce that the above expression is equal to

− ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d}^{2q_{1}+2d−1} s(j) − d.  (3.5)

By the definitions of Q and d, we have Q/2 < 2q_{1} < 2q_{1}+d ≤ Q ≤ 2q_{1}+2d−1 < 2Q. Thus, the above quantity can be further modified to

− ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d}^{Q−1} s(j)+ ∑_{j=Q}^{2q_{1}+2d−1} s(j) − d

= − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d− \frac{Q}{2}}^{\frac{Q}{2} −1} s(j) + ∑_{j=0}^{2q_{1}+2d−Q−1} s(j)

= − ∑_{j=2q_{1}+2d−Q}^{d−1} s(j) + ∑_{j=2q_{1}+d− \frac{Q}{2}}^{\frac{Q}{2} −1} s(j).

From Q/2 < 2q_{1} and 2q_{1} + d ≤ Q, we infer that d < Q/2. Now we use identity (2.4) with 2^{e} = \frac{Q}{2} for all the digit sums in the last expression. This leads to the expression

∑_{j= \frac{Q}{2} −d}^{\frac{3}{2} Q−2q_{1}−2d−1} s(j) − ∑_{j=0}^{Q−2q_{1}−d−1} s(j).

We recall that Q−2q_{1}−d ≥ 0. Apply (2.9) again to conclude that the last expression, and hence, ν_{2}(θ_{q,n}), is zero only if the sums in the last line are empty, that is, if d = Q − 2q_{1}.

Case 1c: Q < 2q_{1} + d and 2q_{1} + 2d ≤ 2Q. In this case, the quantity (3.2) becomes

− ∑_{r=0}^{c−1} ∑_{j=0}^{Q−1} s(rQ + j) − ∑_{j=cQ}^{cQ+d−1} s(j) + ∑_{j=cQ+2q_{1}+d}^{(c+2)Q−1} s(j)

+ ∑_{r=c+2}^{2c} ∑_{j=0}^{Q−1} s(rQ + j) + ∑_{j=(2c+1)Q}^{2cQ+2q_{1}+2d−1} s(j) − (cQ + d)

= −Q ∑_{r=0}^{c−1} s(r) − c ∑_{j=0}^{Q−1} s(j) − ds(c) − ∑_{j=0}^{d−1} s(j) + (2Q − 2q_{1} − d)s(c + 1)

+ ∑_{j=2q_{1}+d−Q}^{Q−1} s(j) + Q ∑_{r=c+2}^{2c} s(r) + (c − 1) ∑_{j=0}^{Q−1} s(j)

+ (2q_{1} + 2d − Q)s(2c + 1) + ∑_{j=0}^{2q_{1}+2d−Q−1} s(j) − (cQ + d)

= Q (− ∑_{r=0}^{c−1} s(r) + ∑_{r=c+1}^{2c} s(r) − c) − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d−Q}^{2q_{1}+2d−Q−1} s(j)

+ (2q_{1} + d − Q)(s(c) − s(c + 1) + 1)
= − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d−Q}^{2q_{1}+2d−Q−1} s(j) + (2q_{1} + d − Q)(s(c) − s(c + 1) + 1). (3.6)

In the second step we used the equality s(2c + 1) = s(c) + 1, and in the last step we used again (2.8). Since Q < 2q_{1}+d, we have 2q_{1}+d−Q > 0. As s(c)−s(c+1)+1 ≥ 0 for any c ≥ 0, the third term in the last line is nonnegative. As d > 0, the inequality (2.9) implies that the sum of the first two terms is strictly positive.

Case 1d: Q < 2q_{1} + d and 2q_{1} + 2d > 2Q. In this case, the quantity (3.2) becomes

− ∑_{r=0}^{c−1} ∑_{j=0}^{Q−1} s(rQ + j) − ∑_{j=cQ}^{cQ+d−1} s(j) + ∑_{j=cQ+2q_{1}+d}^{(c+2)Q−1} s(j)

+ ∑_{r=c+2}^{2c+1} ∑_{j=0}^{Q−1} s(rQ + j) + ∑_{j=(2c+2)Q}^{2cQ+2q_{1}+2d−1} s(j) − (cQ + d)

= −Q ∑_{r=0}^{c−1} s(r) − c ∑_{j=0}^{Q−1} s(j) − ds(c) − ∑_{j=0}^{d−1} s(j) + (2Q − 2q_{1} − d)s(c + 1)

+ ∑_{j=2q_{1}+d−Q}^{Q−1} s(j) + Q ∑_{r=c+2}^{2c+1} s(r) + c ∑_{j=0}^{Q−1} s(j)

+ (2q_{1} + 2d − 2Q)s(2c + 2) + ∑_{j=0}^{2q_{1}+2d−2Q−1} s(j) − (cQ + d).

We now do the following substitutions. First, s(2(c + 1)) = s(c + 1). Second, in the sum over j = 0, …, 2q_{1}+2d−2Q−1 (where 2q_{1}+2d−2Q−1 ≤ Q+2(Q−1)−2Q−1 = Q − 1), we let s(j) = s(Q + j) − 1. Third,

∑_{r=c+2}^{2c+1} s(r) = s(2c + 1) − s(c + 1) + ∑_{r=c+1}^{2c} s(r) = s(c) + 1 − s(c + 1) + ∑_{r=c+1}^{2c} s(r).

Hence, the above expression is equal to

Q (− ∑_{r=0}^{c−1} s(r) + ∑_{r=c+1}^{2c} s(r) − c) − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d−Q}^{Q−1} s(j)

+ ∑_{j=Q}^{2q_{1}+2d−Q−1} s(j) − (2q_{1} + 2d − 2Q) + (Q − d)(s(c) − s(c + 1) + 1)

= − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d−Q}^{2q_{1}+2d−Q−1} s(j) − (2q_{1} + 2d − 2Q) + (Q − d)(s(c) − s(c + 1) + 1), (3.7)

where we used again (2.8). Since Q > d and s(c)−s(c+1)+1 ≥ 0 for any c ≥ 0, the fourth term in the last line is nonnegative. We have \frac{Q}{2} < d < Q and d ≥ 2q_{1} +d−Q. Thus, we may apply (2.7) to deduce that the sum of the first two terms is at least 2q_{1} + d − Q. Hence the expression (3.7) is not less than Q − d > 0.

The proof of Case 1 is completed.

Case 2. Let n = 2n_{1} + 1, q = 2q_{1} + 1, where n_{1} ≥ q_{1} ≥ 0. Write p = n_{1} − q_{1} and substitute in (2.5) to obtain

ν_{2}(θ_{q,n}) = −(n_{1} − q_{1}) − ∑_{j=0}^{n_{1}−q_{1}−1} s(j) + ∑_{j=n_{1}+q_{1}+1}^{2n_{1}} s(j).  (3.8)

We now show that the right-hand side of (3.8) is zero if and only if

n_{1} ≡ q_{1} (mod 2^{⌈log_{2}(2q_{1}+1)⌉})

or

n_{1} ≡ −q_{1} − 1 (mod 2^{⌈log_{2}(2q_{1}+1)⌉}),

which is obviously equivalent to the theorem in this case.

In Case 2 we always use the abbreviation Q = 2^{⌈log_{2}(2q_{1}+1)⌉}. Write n_{1} = cQ + q_{1} + d, where 0 ≤ d < Q. We have to show that the expression (3.8), that is,

− ∑_{j=0}^{n_{1}−q_{1}−1} s(j) + ∑_{j=n_{1}+q_{1}+1}^{2n_{1}} s(j) − (n_{1} − q_{1})

= − ∑_{j=0}^{cQ+d−1} s(j) + ∑_{j=cQ+2q_{1}+d+1}^{2cQ+2q_{1}+2d} s(j) − (cQ + d), (3.9)

is zero only if d = 0 or d = Q−2q_{1} −1. To do so, we distinguish again various cases, depending on the size of d.

Case 2a: 2q_{1} + 2d < Q. In this case, the quantity (3.9) becomes

− ∑_{r=0}^{c−1} ∑_{j=0}^{Q−1} s(rQ + j) − ∑_{j=cQ}^{cQ+d−1} s(j) + ∑_{j=cQ+2q_{1}+d+1}^{(c+1)Q−1} s(j)

+ ∑_{r=c+1}^{2c−1} ∑_{j=0}^{Q−1} s(rQ + j) + ∑_{j=2cQ}^{2cQ+2q_{1}+2d} s(j) − (cQ + d)

= −Q ∑_{r=0}^{c−1} s(r) − c ∑_{j=0}^{Q−1} s(j) − ds(c) − ∑_{j=0}^{d−1} s(j)

+ (Q − 2q_{1} − d − 1)s(c) + ∑_{j=2q_{1}+d+1}^{Q−1} s(j)

+ Q ∑_{r=c+1}^{2c−1} s(r) + (c − 1) ∑_{j=0}^{Q−1} s(j) + (2q_{1} + 2d + 1)s(2c) + ∑_{j=0}^{2q_{1}+2d} s(j) − (cQ + d)

= Q (− ∑_{r=0}^{c−1} s(r) + ∑_{r=c+1}^{2c} s(r) − c) − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d+1}^{2q_{1}+2d} s(j) − d

= − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d+1}^{2q_{1}+2d} s(j) − d,

where in the last line we used again (2.8). The reader should compare this expression with the one in (3.3). Indeed, the remaining arguments are completely analogous to those after (3.3) in Case 1a of the current proof, which are therefore left to the reader.

Case 2b: 2q_{1} + d < Q ≤ 2q_{1} + 2d. In this case, the quantity (3.9) becomes

− ∑_{r=0}^{c−1} ∑_{j=0}^{Q−1} s(rQ + j) − ∑_{j=cQ}^{cQ+d−1} s(j) + ∑_{j=cQ+2q_{1}+d+1}^{(c+1)Q−1} s(j)

+ ∑_{r=c+1}^{2c} ∑_{j=0}^{Q−1} s(rQ + j) + ∑_{j=(2c+1)Q}^{2cQ+2q_{1}+2d} s(j) − (cQ + d)

= −Q ∑_{r=0}^{c−1} s(r) − c ∑_{j=0}^{Q−1} s(j) − ds(c) − ∑_{j=0}^{d−1} s(j)

+ (Q − 2q_{1} − d − 1)s(c) + ∑_{j=2q_{1}+d+1}^{Q−1} s(j)

+ Q ∑_{r=c+1}^{2c} s(r) + c ∑_{j=0}^{Q−1} s(j) + (2q_{1} + 2d + 1 − Q)s(2c) + ∑_{j=Q}^{2q_{1}+2d} s(j) − (cQ + d)

= Q (− ∑_{r=0}^{c−1} s(r) + ∑_{r=c+1}^{2c} s(r) − c) − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d+1}^{2q_{1}+2d} s(j) − d

= − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d+1}^{2q_{1}+2d} s(j) − d,

where in the last line we used again (2.8). The reader should compare this expression with the one in (3.5). Indeed, the remaining arguments are completely analogous to those after (3.5) in Case 1b of the current proof, which are therefore left to the reader.

Case 2c. Q ≤ 2q_{1} + d and 2q_{1} + 2d < 2Q. In this case, the quantity (3.9) becomes

− ∑_{r=0}^{c−1} ∑_{j=0}^{Q−1} s(rQ + j) − ∑_{j=cQ}^{cQ+d−1} s(j) + ∑_{j=cQ+2q_{1}+d+1}^{(c+2)Q−1} s(j)

+ ∑_{r=c+2}^{2c} ∑_{j=0}^{Q−1} s(rQ + j) + ∑_{j=(2c+1)Q}^{2cQ+2q_{1}+2d} s(j) − (cQ + d)

= −Q ∑_{r=0}^{c−1} s(r) − c ∑_{j=0}^{Q−1} s(j) − ds(c) − ∑_{j=0}^{d−1} s(j) + (2Q − 2q_{1} − d − 1)s(c + 1)

+ ∑_{j=2q_{1}+d+1−Q}^{Q−1} s(j) + Q ∑_{r=c+2}^{2c} s(r) + (c − 1) ∑_{j=0}^{Q−1} s(j)

+ (2q_{1} + 2d + 1 − Q)s(2c + 1) + ∑_{j=0}^{2q_{1}+2d−Q} s(j) − (cQ + d)

= Q (− ∑_{r=0}^{c−1} s(r) + ∑_{r=c+1}^{2c} s(r) − c) − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d+1−Q}^{2q_{1}+2d−Q} s(j)

+ (2q_{1} + d + 1 − Q)(s(c) − s(c + 1) + 1)

= − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d+1−Q}^{2q_{1}+2d−Q} s(j) + (2q_{1} + d + 1 − Q)(s(c) − s(c + 1) + 1),

where in the last step we used again (2.8). Since Q < 2q_{1} + d + 1, we have 2q_{1} + d + 1 − Q > 0. In particular, since also s(c) − s(c + 1) + 1 ≥ 0 for any c, the third term in the last line is nonnegative, and, because d > 0, the inequality (2.9) says that the sum of the first two terms is strictly positive.

Case 2d. Q ≤ 2q_{1} + d and 2q_{1} + 2d ≥ 2Q. In this case, the quantity (3.9) becomes

− ∑_{r=0}^{c−1} ∑_{j=0}^{Q−1} s(rQ + j) − ∑_{j=cQ}^{cQ+d−1} s(j) + ∑_{j=cQ+2q_{1}+d+1}^{(c+2)Q−1} s(j)

+ ∑_{r=c+2}^{2c+1} ∑_{j=0}^{Q−1} s(rQ + j) + ∑_{j=(2c+2)Q}^{2cQ+2q_{1}+2d} s(j) − (cQ + d)

= −Q ∑_{r=0}^{c−1} s(r) − c ∑_{j=0}^{Q−1} s(j) − ds(c) − ∑_{j=0}^{d−1} s(j) + (2Q − 2q_{1} − d − 1)s(c + 1)

+ ∑_{j=2q_{1}+d+1−Q}^{Q−1} s(j) + Q ∑_{r=c+2}^{2c+1} s(r) + c ∑_{j=0}^{Q−1} s(j)

+ (2q_{1} + 2d + 1 − 2Q)s(2c + 2) + ∑_{j=0}^{2q_{1}+2d−2Q} s(j) − (cQ + d)

= Q (− ∑_{r=0}^{c−1} s(r) + ∑_{r=c+1}^{2c} s(r) − c) − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d+1−Q}^{Q−1} s(j)

+ ∑_{j=Q}^{2q_{1}+2d−Q} s(j) − (2q_{1} + 2d − 2Q + 1) + (Q − d)(s(c) − s(c + 1) + 1)

= − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d+1−Q}^{2q_{1}+2d−Q} s(j)

− (2q_{1} + 2d − 2Q + 1) + (Q − d)(s(c) − s(c + 1) + 1),

where in the last step we used again (2.8). We have d < Q. In particular, since also s(c) − s(c + 1) + 1 ≥ 0 for any c, the fourth term in the last line is nonnegative. Moreover, because 2q_{1} + d + 1 − Q ≤ d, the inequality (2.7) says that the sum of the first two terms is at least 2q_{1} + d + 1 − Q = (2q_{1} + 2d − 2Q + 1) + (Q − d). Thus, the sum of the first three terms in the last line is strictly positive. Combining both findings, we infer that the whole last line is strictly positive (in fact, at least Q − d).

This finishes the proof of Case 2 and, thus, of the theorem.

4 Additional results on the 2-adic valuation of δ_{n−q,n} = θ_{q,n}

In this section, we examine the 2-adic behavior of θ_{q,n} = δ_{n−q,n} in more detail. Keeping in mind Proposition 2.1, we concentrate throughout this section on the case that n and q have the same parity.

If we fix q and let n = q + 2i, i = 0, 1, 2, …, vary, then we know that whenever (1.4) is satisfied, the 2-adic valuation of θ_{q,n} = θ_{q,q+2i} will be zero. However, what happens in between? By looking at some random values of q, one might get the impression that, between two successive occurrences of zero, the 2-adic valuations ν_{2}(θ_{q,q+2i}) are unimodal, that is, they first grow (weakly) monotone until they reach their maximum value half-way, and then they drop (weakly) monotone until they come back to zero in the end. Moreover, one is led to guess that the 2-adic valuations are symmetric around the place where the maximum is attained. As it turns out (see Example 4.1 below), the unimodality conjecture is not true, while the symmetry conjecture is indeed true. However, in some sense, unimodality is “almost” true. As we demonstrate in Theorems 4.2, 4.4, 4.6, 4.8 below, between two successive values of zero, the 2-adic valuations ν_{2}(θ_{q,q+2i}) stay above a linear function of slope 1 which is tight at the opening zero, and at the same time they stay below another linear function of slope 1 which is tight at the maximum (see (4.1) and (4.2) in Theorem 4.2 and the analogous inequalities in the subsequent theorems), until they reach the maximum value, which is attained exactly half-way, and the 2-adic valuations beyond are the symmetric images of those before. In the theorems, we determine in addition the maximal value for each of these intervals.

The results which are found on the way to prove these theorems allow one also to address the following question: characterize all values of q and n for which the 2-adic valuation of θ_{q,n} has a certain fixed (small) value. Clearly, Theorem 3.1 does this if we fix this value to 0. In Corollaries 4.3, 4.5, 4.7, 4.9 we work out the analogous characterization if we fix this value to 1. We could move on to 2, 3, etc., but at the cost of a considerable increase of complication the further we go.

Example 4.1. The sequence (ν_{2}(θ_{q,q+2i}))_{i≥0} is not unimodal in the intervals discussed in Theorems 4.2–4.8 (although the theorems show that it comes very close). Here we give two counter-examples.

Consider q = 39. In this case, the first 200 terms of the sequence (ν_{2}(θ_{q,q+2i}))_{i≥0} are:

0,1, 3, 5, 7, 8, 8, 8, 8, 9, 12, 15, 18, 18, 15, 12, 9, 8, 8, 8, 8, 7, 5, 3, 1, 0, 3, 6, 9, 10, 9, 8, 7, 9,

12, 15, 18, 20, 21, 22, 23, 25, 29, 33, 37, 37, 33, 29, 25, 23, 22, 21, 20, 18, 15, 12, 9, 7, 8, 9, 10, 9, 6, 3, 0, 1, 3, 5, 7, 8, 8, 8, 8, 9, 12, 15, 18, 18, 15, 12, 9, 8, 8, 8, 8, 7, 5, 3, 1, 0, 4, 8, 12, 14, 14, 14, 14, 17, 21, 25, 29, 32, 34, 36, 38, 41, 46, 51, 56, 56, 51, 46, 41, 38, 36, 34, 32, 29, 25, 21, 17, 14, 14, 14, 14, 12, 8, 4, 0, 1, 3, 5, 7, 8, 8, 8, 8, 9, 12, 15, 18, 18, 15, 12, 9, 8, 8, 8, 8, 7, 5, 3, 1, 0, 3, 6, 9, 10, 9, 8, 7, 9, 12, 15, 18, 20, 21, 22, 23, 25, 29, 33, 37, 37, 33, 29, 25, 23, 22, 21, 20, 18, 15, 12, 9, 7, 8, 9, 10, 9, 6, 3, 0, 1, 3, 5, 7, 8, 8, 8, 8.

As predicted by Theorem 3.1, zeros occur for all multiples of \frac{1}{2}2^{⌈log_{2} 2·39⌉} = 64 and for multiples of 64 reduced by 39. However, while the first interval (the interval comprising the first 25 values) is unimodal, the second one (comprising the next 39 values) is not, as can be seen from the subsequence 0, 3, 6, 9, 10, 9, 8, 7, 9, 12, 15, …, 37, …, which rises first to 10, then drops to 7, to rise again beyond 10 until it reaches the maximum of 37 in this interval.

Consider now q = 46. In this case, the first 200 terms are:

0,4, 2, 5, 6, 10, 10, 13, 14, 19, 14, 13, 10, 10, 6, 5, 2, 4, 0, 3, 4, 8, 8, 11, 12, 17, 14, 15, 14, 16,

14, 15, 14, 19, 18, 22, 24, 29, 30, 34, 36, 42, 36, 34, 30, 29, 24, 22, 18, 19, 14, 15, 14, 16, 14, 15, 14, 17, 12, 11, 8, 8, 4, 3, 0, 4, 2, 5, 6, 10, 10, 13, 14, 19, 14, 13, 10, 10, 6, 5, 2, 4, 0, 4, 6, 11, 12, 16, 18, 24, 22, 24, 24, 27, 26, 28, 28, 34, 34, 39, 42, 48, 50, 55, 58, 65, 58, 55, 50, 48, 42, 39, 34, 34, 28, 28, 26, 27, 24, 24, 22, 24, 18, 16, 12, 11, 6, 4, 0, 4, 2, 5, 6, 10, 10, 13, 14, 19, 14, 13, 10, 10, 6, 5, 2, 4, 0, 3, 4, 8, 8, 11, 12, 17, 14, 15, 14, 16, 14, 15, 14, 19, 18, 22, 24, 29, 30, 34, 36, 42, 36, 34, 30, 29, 24, 22, 18, 19, 14, 15, 14, 16, 14, 15, 14, 17, 12, 11, 8, 8, 4, 3, 0, 4, 2, 5, 6, 10, 10, 13, 14.

This is an example where both types of intervals are not unimodular. The first interval (comprising the first 64 − 46 = 18 values) begins 0, 4, 2, 5, 6, 10, 10, 13, 14, 19, …, that is, rises to 4, drops to 2, before rising again up to the maximum of 19 in this interval. The second one (comprising the next 46 values) starts by 0, 3, 4, 8, 8, 11, 12, 17, 14, 15, …, 42, …, that is, rises to 17, drops to 14, before rising again up to the maximum of 42 in this interval. Similar remarks apply to the subsequent intervals.

Nevertheless, between two successive zeros, although the 2-adic valuations ν_{2}(θ_{q,q+2i}) are not unimodal in general, the 2-adic valuations still seem to exhibit an overall increase until a maximum halfway and then a decrease which is the symmetric image of the increasing values. In the theorems below, we quantify this statement. We split our results into four separate theorems. On the one hand, we have to distinguish between the two possible parities of q, and, on the other hand, for each integer q, there are two types of intervals to be considered.

Theorem 4.2. Let q be a fixed positive even integer, Q = 2^{⌈log_{2} q⌉}, and let c be any nonnegative integer. Then the values of the sequence (ν_{2}(θ_{q,q+2i}))_{i≥0} for i ∈ [cQ, (c + 1)Q − q] are symmetric around its center i_{1} = cQ + (Q − q)/2. The values at the extreme points of the interval i = cQ and i = (c + 1)Q − q are 0, and the value at the center is

ν_{2}(θ_{q,q+2i_{1}}) = \frac{Q − q}{2} log_{2} \frac{Q}{2} − 2 ∑_{j=0}^{\frac{Q−q−2}{2}} s(j),

independent of c. Furthermore, for i ∈ [cQ, i_{1}] the inequalities

ν_{2}(θ_{q,q+2i}) ≥ i − cQ  (4.1)

and

ν_{2}(θ_{q,q+2i}) ≤ ν_{2}(θ_{q,q+2i_{1}}) − (i_{1} − i)  (4.2)

hold.

Proof. In this proof, we use again the notation q_{1} = q/2. To show the symmetry write i = cQ + d with 0 ≤ d ≤ Q − 2q_{1}. In particular, we have 2q_{1} + d ≤ Q, and, hence (cf. (3.3) and (3.5)), the 2-adic valuation of θ_{q,q+2i} is given by

ν_{2}(θ_{q,q+2i}) = ν_{2}(θ_{q,q+2(cQ+d)}) = − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d}^{2q_{1}+2d−1} s(j) − d.  (4.3)

On the other hand, for the same reason, the 2-adic valuation of θ_{q,q+2(cQ+Q−q−d)} is given by

ν_{2}(θ_{q,q+2(cQ+Q−2q_{1}−d)}) = − ∑_{j=0}^{Q−2q_{1}−d−1} s(j) + ∑_{j=2q_{1}+(Q−2q_{1}−d)}^{2q_{1}+2(Q−2q_{1}−d)−1} s(j) − (Q − 2q_{1} − d)

= − ∑_{j=0}^{Q−2q_{1}−d−1} s(j) + ∑_{j=Q−d}^{2Q−2q_{1}−2d−1} s(j) − (Q − 2q_{1} − d)

= − ∑_{j=0}^{Q−1} s(j) + ∑_{j=Q−2q_{1}−d}^{Q−1} s(j)

+ ∑_{j=0}^{2Q−1} s(j) − ∑_{j=0}^{Q−d−1} s(j) − ∑_{j=2Q−2q_{1}−2d}^{2Q−1} s(j) − (Q − 2q_{1} − d)

= ∑_{j=Q−2q_{1}−d}^{Q−1} s(j) + ∑_{j=Q}^{2Q−1} s(j) − ∑_{j=0}^{Q−d−1} s(j) − ∑_{j=2Q−2q_{1}−2d}^{2Q−1} s(j) − (Q − 2q_{1} − d)

= ∑_{j=Q−2q_{1}−d}^{Q−1} s(j) + ∑_{j=Q−d}^{Q−1} s(j) − ∑_{j=2Q−2q_{1}−2d}^{2Q−1} s(j) + (2q_{1} + d).

Now we apply the reflection identity (2.4) to all the sum of digit functions. Thus, we obtain

ν_{2}(θ_{q,q+2(cQ+Q−2q_{1}−d)}) = (2q_{1} + 2d) log_{2} Q − ∑_{j=0}^{2q_{1}+d−1} s(j) − ∑_{j=0}^{d−1} s(j)

− (2q_{1} + 2d) log_{2}(2Q) + ∑_{j=0}^{2q_{1}+2d−1} s(j) + (2q_{1} + d)

= − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d}^{2q_{1}+2d−1} s(j) − d

= ν_{2}(θ_{q,q+2(cQ+d)}),

proving the symmetry. That the values of the extreme points of the interval i = cQ and i = (c + 1)Q − q are 0, was already shown in Theorem 3.1, Case 1.

Next we determine the 2-adic value of θ_{q,q+2i} at the center i_{1} = cQ + (Q − q)/2 of the interval. By (4.3), we have

ν_{2}(θ_{q,q+2i_{1}}) = ν_{2}(θ_{q,q+2(cQ+Q/2−q_{1})})

= − ∑_{j=0}^{\frac{Q}{2} −q_{1}−1} s(j) + ∑_{j= \frac{Q}{2} +q_{1}}^{Q−1} s(j) − (\frac{Q}{2} − q_{1})

= − ∑_{j=0}^{\frac{Q}{2} −q_{1}−1} s(j) + ∑_{j=q_{1}}^{\frac{Q}{2} −1} s(j)

= (\frac{Q}{2} − q_{1}) log_{2} \frac{Q}{2} − 2 ∑_{j=0}^{\frac{Q}{2} −q_{1}−1} s(j).

To prove the inequality (4.1), we write again i = cQ + d, with d ≤ Q/2 − q_{1}. Under this condition, we showed in the proof of Theorem 3.1, Case 1a (see (3.4)), that ν_{2}(θ_{q,q+2i}) can be written in the form

ν_{2}(θ_{q,q+2i}) = ν_{2}(θ_{q,q+2(cQ+d)}) = − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d− \frac{Q}{2}}^{2q_{1}+2d− \frac{Q}{2} −1} s(j).  (4.4)

Since d ≤ 2q_{1} + d − Q, the inequality (2.6) implies that this expression is at least d = i − cQ.

To prove inequality (4.2), we compute the difference of the 2-adic valuations of θ_{q,q+2i_{1}} and θ_{q,q+2i} for i ∈ [cQ, i_{1}]: let again i = cQ + d, 0 ≤ d ≤ (Q − q)/2. Then, using (4.3), we have

ν_{2}(θ_{q,q+2i_{1}}) − ν_{2}(θ_{q,q+2i}) = ν_{2}(θ_{q,q+2(cQ+Q/2−q_{1})}) − ν_{2}(θ_{q,q+2(cQ+d)})

= − ∑_{j=0}^{\frac{Q}{2} −q_{1}−1} s(j) + ∑_{j= \frac{Q}{2} +q_{1}}^{Q−1} s(j) − (\frac{Q}{2} − q_{1})

+ ∑_{j=0}^{d−1} s(j) − ∑_{j=2q_{1}+d}^{2q_{1}+2d−1} s(j) + d

= − ∑_{j=d}^{\frac{Q}{2} −q_{1}−1} s(j) − ∑_{j=2q_{1}+d}^{\frac{Q}{2} +q_{1}−1} s(j) + ∑_{j=2q_{1}+2d}^{Q−1} s(j) − (\frac{Q}{2} − q_{1} − d) .

Now we apply the reflection formula (2.4) to all the sum of digits functions. This yields

ν_{2}(θ_{q,q+2i_{1}}) − ν_{2}(θ_{q,q+2i}) = ∑_{j=q_{1}}^{\frac{Q}{2} −d−1} s(j) + ∑_{j= \frac{Q}{2} −q_{1}}^{Q−2q_{1}−d−1} s(j) − ∑_{j=0}^{Q−2q_{1}−2d−1} s(j)

= ∑_{j=q_{1}}^{\frac{Q}{2} −d−1} s(j) + ∑_{j= \frac{Q}{2} −q_{1}}^{Q−2q_{1}−d−1} s(j) − ∑_{j=0}^{\frac{Q}{2} −q_{1}−d−1}(s(2j) + s(2j + 1))

= ∑_{j=q_{1}}^{\frac{Q}{2} −d−1} s(j) + ∑_{j= \frac{Q}{2} −q_{1}}^{Q−2q_{1}−d−1} s(j) − 2 ∑_{j=0}^{\frac{Q}{2} −q_{1}−d−1} s(j) − (\frac{Q}{2} − q_{1} − d) .

Since q_{1} ≥ \frac{Q}{2} − q_{1} ≥ \frac{Q}{2} − q_{1} − d, we may apply (2.6) twice to obtain finally

ν_{2}(θ_{q,q+2i_{1}}) − ν_{2}(θ_{q,q+2i}) ≥ (\frac{Q}{2} − q_{1} − d) = i_{1} − i,

as desired.

Corollary 4.3. For a fixed even q, the values of the sequence (ν_{2}(θ_{q,q+2i}))_{i≥0} are never 1 for i ∈ [cQ, (c + 1)Q − q].

Proof. By the symmetry of the values around the center of the interval, and by the inequality (4.1), the only possible candidates are i = cQ+1 and i = (c+1)Q−q −1. Formula (4.4) for ν_{2}(θ_{q,q+2i}) implies that in that case we must have

s (q + 1 − \frac{Q}{2}) = 1.

This is only possible if q + 1 − \frac{Q}{2} is a power of 2, and this, in its turn, implies that q must be odd, a contradiction.

Theorem 4.4. Let q be a fixed positive even integer, Q = 2^{⌈log_{2} q⌉}, and let c be any nonnegative integer. Then the values of the sequence (ν_{2}(θ_{q,q+2i}))_{i≥0} for i ∈ [(c + 1)Q − q, (c + 1)Q] are symmetric around its center i_{2} = (c + 1)Q − q/2. The values at the extreme points of the interval i = (c + 1)Q − q and i = (c + 1)Q are 0, and the value at the center is

ν_{2}(θ_{q,q+2i_{2}}) = \frac{q}{2} log_{2} Q − 2 ∑_{j=0}^{\frac{q−2}{2}} s(j) + \frac{q}{2}(s(c) − s(c + 1) + 1).

Furthermore, for i ∈ [i_{2}, (c + 1)Q] the inequalities

ν_{2}(θ_{q,q+2i}) ≥ (c + 1)Q − i  (4.5)

and

ν_{2}(θ_{q,q+2i}) ≤ ν_{2}(θ_{q,q+2i_{2}}) − (i − i_{2})  (4.6)

hold.

Proof. We use again the notation q_{1} = q/2. To show the symmetry write i = cQ + d with Q−2q_{1} ≤ d ≤ Q. In particular, we have 2q_{1} +d ≥ Q, and, hence, if d ≤ Q−q_{1}, the 2-adic valuation of θ_{q,q+2i} is given by (cf. (3.6), which also holds if 2q_{1} + d = Q as the quantity vanishes in this case)

ν_{2}(θ_{q,q+2i}) = ν_{2}(θ_{q,q+2(cQ+d)})

= − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d−Q}^{2q_{1}+2d−Q−1} s(j) + (2q_{1} + d − Q)(s(c) − s(c + 1) + 1), (4.7)

while, if d > Q − q_{1}, it is given by (cf. (3.7))

ν_{2}(θ_{q,q+2i}) = ν_{2}(θ_{q,q+2(cQ+d)})

− ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d−Q}^{2q_{1}+2d−Q−1} s(j) − (2q_{1} + 2d − 2Q) + (Q − d)(s(c) − s(c + 1) + 1). (4.8)

Now let i > i_{2}, that is, d > Q − q_{1}. Symmetry around the center i_{2} = (c + 1)Q − q_{1} means to show that

ν_{2}(θ_{q,q+2(cQ+2Q−q−d)}) = ν_{2}(θ_{q,q+2(cQ+d)}).

Using (4.7), the left-hand term is given by

ν_{2}(θ_{q,q+2((c+2)Q−2q_{1}−d)})

= − ∑_{j=0}^{2Q−2q_{1}−d−1} s(j) + ∑_{j=Q−d}^{3Q−2q_{1}−2d−1} s(j) + (Q − d)(s(c) − s(c + 1) + 1)

= − ∑_{j=0}^{Q−1} s(j) + ∑_{j=2Q−2q_{1}−d}^{Q−1} s(j) + ∑_{j=0}^{2Q−1} s(j) − ∑_{j=0}^{Q−d−1} s(j) − ∑_{j=3Q−2q_{1}−2d}^{2Q−1} s(j)

+ (Q − d)(s(c) − s(c + 1) + 1)

= ∑_{j=2Q−2q_{1}−d}^{Q−1} s(j) + ∑_{j=Q}^{2Q−1} s(j) − ∑_{j=0}^{Q−d−1} s(j) − ∑_{j=3Q−2q_{1}−2d}^{2Q−1} s(j)

+ (Q − d)(s(c) − s(c + 1) + 1)

= ∑_{j=2Q−2q_{1}−d}^{Q−1} s(j) + ∑_{j=Q−d}^{Q−1} s(j) + Q − ∑_{j=3Q−2q_{1}−2d}^{2Q−1} s(j)

+ (Q − d)(s(c) − s(c + 1) + 1).

Now we apply the reflection identity (2.4) to all the sum of digit functions. Thus, we obtain

ν_{2}(θ_{q,q+2((c+2)Q−2q_{1}−d)}) = (2q_{1} + 2d − Q) log_{2} Q − ∑_{j=0}^{2q_{1}+d−Q−1} s(j) − ∑_{j=0}^{d−1} s(j)

− (2q_{1} + 2d − Q) log_{2}(2Q) + ∑_{j=0}^{2q_{1}+2d−Q−1} s(j)

+ Q + (Q − d)(s(c) − s(c + 1) + 1)

= − ∑_{j=0}^{d−1} s(j) + ∑_{j=2q_{1}+d−Q}^{2q_{1}+2d−Q−1} s(j) − (2q_{1} + 2d − 2Q) + (Q − d)(s(c) − s(c + 1) + 1)

= ν_{2}(θ_{q,q+2(cQ+d)}),

by (4.8), as desired. That the values at the extreme points of the interval i = (c + 1)Q − q and i = (c + 1)Q are 0, was already shown in Theorem 3.1, Case 1.

Next we determine the 2-adic value of θ_{q,q+2i} at the center i_{2} = (c + 1)Q − q/2 of the interval. By (4.7), we have

ν_{2}(θ_{q,q+2i_{2}}) = ν_{2}(θ_{q,q+2((c+1)Q−q_{1})})

= − ∑_{j=0}^{Q−q_{1}−1} s(j) + ∑_{j=q_{1}}^{Q−1} s(j) + q_{1}(s(c) − s(c + 1) + 1)

= − ∑_{j=0}^{q_{1}−1} s(j) + ∑_{j=Q−q_{1}}^{Q−1} s(j) + q_{1}(s(c) − s(c + 1) + 1)

= q_{1} log_{2} Q − 2 ∑_{j=0}^{q_{1}−1} s(j) + q_{1}(s(c) − s(c + 1) + 1).

Inequality (4.5) was already implicitly proved in the proof of Theorem 3.1, Case 1d. Namely, if i = cQ + d, with d ≥ Q − q_{1}, then the conditions of Case 1d are satisfied, and there it was shown (see the paragraph after (3.7)) that

ν_{2}(θ_{q,q+2i}) = ν_{2}(θ_{q,q+2(cQ+d)}) ≥ Q − d = (c + 1)Q − i,

as desired.

To prove inequality (4.6), we compute the difference of the 2-adic valuations of θ_{q,q+2i_{2}} and θ_{q,q+2i} for i ∈ [i_{2}, (c+1)Q]: let again i = cQ+d, Q−q_{1} ≤ d ≤ Q. Then, using (4.8) again, we have

ν_{2}(θ_{q,q+2i_{2}}) − ν_{2}(θ_{q,q+2i}) = ν_{2}(θ_{q,q+2((c+1)Q−q_{1})}) − ν_{2}(θ_{q,q+2(cQ+d)})

= − ∑_{j=0}^{Q−q_{1}−1} s(j) + ∑_{j=q_{1}}^{Q−1} s(j) + q_{1}(s(c) − s(c + 1) + 1) + ∑_{j=0}^{d−1} s(j)

− ∑_{j=2q_{1}+d−Q}^{2q_{1}+2d−Q−1} s(j) + (2q_{1} + 2d − 2Q) − (Q − d)(s(c) − s(c + 1) + 1)

= ∑_{j=Q−q_{1}}^{d−1} s(j) + ∑_{j=q_{1}}^{2q_{1}+d−Q−1} s(j) − ∑_{j=Q}^{2q_{1}+2d−Q−1} s(j)

+ (q_{1} + d − Q)(s(c) − s(c + 1) + 3)

= ∑_{j=Q−q_{1}}^{d−1} s(j) + ∑_{j=q_{1}}^{2q_{1}+d−Q−1} s(j) − ∑_{j=0}^{2q_{1}+2d−2Q−1} s(j)

+ (q_{1} + d − Q)(s(c) − s(c + 1) + 1)

= ∑_{j=Q−q_{1}}^{d−1} s(j) + ∑_{j=q_{1}}^{2q_{1}+d−Q−1} s(j)

− 2 ∑_{j=0}^{q_{1}+d−Q−1} s(j) + (q_{1} + d − Q)(s(c) − s(c + 1)).

Since Q − q_{1} ≥ q_{1} + d − Q and q_{1} ≥ q_{1} + d − Q, we may apply the inequality (2.6) twice to obtain

ν_{2}(θ_{q,q+2i_{2}}) − ν_{2}(θ_{q,q+2i}) ≥ (q_{1} + d − Q)(s(c) − s(c + 1) + 2).

As we used already quite often, s(c) − s(c + 1) + 1 ≥ 0. Therefore,

ν_{2}(θ_{q,q+2i_{2}}) − ν_{2}(θ_{q,q+2i}) ≥ q_{1} + d − Q = i − i_{2},

as desired.

Corollary 4.5. For a fixed even q, the values of the sequence (ν_{2}(θ_{q,q+2i}))_{i≥0} are never 1 for i ∈ [(c + 1)Q − q, (c + 1)Q], except if q is a power of 2 and c is even. In the latter case, ν_{2}(θ_{q,q+2i}) is equal to 1 for i = (c + 1)Q − q − 1 and for i = (c + 1)Q − 1.

Proof. By the symmetry of the values around the center of the interval, and by the inequality (4.5), the only possible candidates are i = (c + 1)Q − q + 1 and i = (c + 1)Q − 1. Let us concentrate on i = (c + 1)Q − 1, which, as before, we write using the parameter d as i = (c + 1)Q − 1 = cQ + d. The formula (3.7) in the proof of Theorem 3.1, Case 1d, (which we used to prove (4.5)), yields that ν_{2}(θ_{q,q+2i}) is equal to

− ∑_{j=0}^{Q−2} s(j) + ∑_{j=q−1}^{q+Q−3} s(j) − (q − 2) + (s(c) − s(c + 1) + 1)

= − ∑_{j=0}^{Q−1} s(j) + s(Q − 1) + ∑_{j=q−1}^{q+Q−2} s(j) − s(q + Q − 2)

− (q − 2) + (s(c) − s(c + 1) + 1)

= ⌈log_{2} q⌉ − s(q + Q − 2) + 1 + (s(c) − s(c + 1) + 1).

For this expression to be equal to 1, we must have s(q + Q − 2) = ⌈log_{2} q⌉ and s(c) − s(c + 1) + 1 = 0. The former is the case if and only if q = Q, that is, if q is a power of 2, and the latter is the case if and only if c is even.

In an analogous manner, one can prove the following two theorems, with accompanying corollaries, covering the case where q is odd.

Theorem 4.6. Let q be a fixed positive odd integer, Q = 2^{⌈log_{2} q⌉}, and let c be any nonnegative integer. Then the values of the sequence (ν_{2}(θ_{q,q+2i}))_{i≥0} for i ∈ [cQ, (c + 1)Q − q] are symmetric around its center cQ + (Q − q)/2. The values at the extreme points of the interval i = cQ and i = (c + 1)Q − q are 0, and the value at the central points i_{3} = cQ + (Q − q − 1)/2 and cQ + (Q − q + 1)/2 is

ν_{2}(θ_{q,q+2i_{3}}) = \frac{Q − q − 1}{2} log_{2} \frac{Q}{2} − 2 ∑_{j=0}^{\frac{Q−q−3}{2}} s(j) − s (\frac{Q − q − 1}{2}) ,

independent of c. Furthermore, for i ∈ [cQ, i_{3}] the inequalities

ν_{2}(θ_{q,q+2i}) ≥ i − cQ  (4.9)

and

ν_{2}(θ_{q,q+2i}) ≤ ν_{2}(θ_{q,q+2i_{3}}) − (i_{3} − i)  (4.10)

hold.

Corollary 4.7. For a fixed odd q, the values of the sequence (ν_{2}(θ_{q,q+2i}))_{i≥0} are never 1 for i ∈ [cQ, (c + 1)Q − q], except if q has the form 2^{M} + 2^{m} − 1, for some positive integers m and M, m < M. In the latter case, ν_{2}(θ_{q,q+2i}) is equal to 1 for i = cQ + 1 and for i = (c + 1)Q − q − 1.

Proof. The arguments from the proof of Corollary 4.3 apply also here. Thus, again, the only possible candidates are i = cQ + 1 and i = (c + 1)Q − q − 1. Furthermore, we must have

s (q + 1 − \frac{Q}{2}) = 1.

This is only possible if q + 1 − \frac{Q}{2} is a power of 2, which means that q has the form given in the statement of the corollary.

Theorem 4.8. Let q be a fixed positive odd integer, Q = 2^{⌈log_{2} q⌉}, and let c be any nonnegative integer. Then the values of the sequence (ν_{2}(θ_{q,q+2i}))_{i≥0} for i ∈ [(c + 1)Q − q, (c + 1)Q] are symmetric around its center (c + 1)Q − q/2. The values at the extreme points of the interval i = (c + 1)Q − q and i = (c + 1)Q are 0, and the value at the central points i_{4} = (c + 1)Q − (q + 1)/2 and (c + 1)Q − (q − 1)/2 is

ν_{2}(θ_{q,q+2i_{4}}) = \frac{q − 1}{2} log_{2} Q − 2 ∑_{j=0}^{\frac{q−3}{2}} s(j) − s (\frac{q − 1}{2}) + \frac{q − 1}{2}(s(c) − s(c + 1) + 1).

Furthermore, for i ∈ [i_{4}, (c + 1)Q] the inequalities

ν_{2}(θ_{q,q+2i}) ≥ (c + 1)Q − i  (4.11)

and

ν_{2}(θ_{q,q+2i}) ≤ ν_{2}(θ_{q,q+2i_{4}}) − (i − i_{4})  (4.12)

hold.

Corollary 4.9. For a fixed odd q, the values of the sequence (ν_{2}(θ_{q,q+2i}))_{i≥0} are never 1 for i ∈ [(c + 1)Q − q, (c + 1)Q].

Proof. The arguments from the proof of Corollary 4.5 apply also here. The conclusion was that we can have ν_{2}(θ_{q,q+2i}) = 1, for some i, only if q is a power of 2. This is a contradiction to our assumption that q is odd.

5 Skew symmetric matrices and the parity of ε_{2p,n}

Let 𝔽 = ℂ, ℝ and denote by GL(n, 𝔽) ⊂ M_{n}(𝔽) the group of n×n invertible matrices. Recall that A_{n}(𝔽) is the linear space of n × n skew symmetric matrices A of order n over 𝔽, i.e., A^{⊤} = −A. Clearly dim A_{n}(𝔽) = \binom{n}{2}. Two matrices A, B ∈ A_{n}(𝔽) are called congruent if A = T BT^{⊤} for some T ∈ GL(n, 𝔽). Let S_{2} := ( \begin{matrix}0 & 1 \\ −1 & 0 \end{matrix} ). The following result is well-known in the real case, but its complex version does not seem to appear in standard modern books on linear algebra.

Proposition 5.1. Let 𝔽 = ℝ, ℂ and A ∈ A_{n}(𝔽). Then A has even rank, 2p say, and A is congruent over 𝔽 to a direct sum of p copies of S_{2} and the (n−2p)×(n−2p) zero matrix. In particular, B ∈ A_{n}(𝔽) is congruent to A over 𝔽 if and only if rank A = rank B.

Proof. We first prove the fact that any A ∈ A_{n}(𝔽) is congruent to the direct sum of copies of S_{2} and 0. The result is trivial if A = 0. Let n = 2 and rank A = 2. Then A = aS_{2} for some 0 ≠ a ∈ 𝔽. For 𝔽 = ℂ we have A = (\sqrt{a}I_{2})S_{2}(\sqrt{a}I_{2})^{⊤}. For 𝔽 = ℝ and a > 0 the above formula holds. For a < 0 we have A = (\sqrt{−a}P)S_{2}(\sqrt{−a}P)^{⊤},

where P := ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ).

Assume by induction that any A ∈ A_{n}(𝔽) is congruent to the direct sum of copies of S_{2} and 0 ∈ M_{n}(𝔽) for n = m ≥ 2. Let n = m+1 and A ∈ A_{m+1}(𝔽). Suppose first that det A = 0. Let 0 ≠ x ∈ 𝔽^{n} and Ax = 0. Let Q ∈ GL(m + 1, F) such that the last column of Q^{⊤} is x. Then QAQ^{⊤} = A_{1} ⊕ 0, and A_{1} ∈ A_{m}(𝔽). Use the induction hypothesis to deduce that A is conjugate to the direct sum of copies of S_{2} and 0. It remains to study the case where m+1 is even and det A ≠ 0. Let A = (a_{ij})_{i,j=1}^{m+1} and A_{1} = (a_{ij})_{i,j=1}^{m} ∈ A_{m}(𝔽). Since A has rank m + 1, A_{1} has at least rank m − 1. Since m is odd A_{1} has exactly rank m−1. So A_{1} is conjugate to a direct sum of \frac{m−1}{2} copies of S_{2} and one copy of 0. Using the corresponding congruence on A, we may assume without loss of generality that A_{1} = (⨁_{i=1}^{(m−1)/2} S_{2}) ⊕ 0. For each i = 1, …, m − 1 subtract from column m + 1 of A the corresponding multiple of column i to obtain the zero element for the (i, m + 1)-entry. Repeat these elementary operations with the rows of A to eliminate the (m + 1, i)-entry for i = 1, …, m − 1. The resulting matrix is of the form B = (⨁_{i=1}^{(m−1/2)} S_{2})⊕bS_{2}. Clearly A is congruent to B. Hence b ≠ 0. Since bS_{2} is congruent to S_{2}, we deduce that A is congruent to a direct sum of copies of S_{2}.

Since a direct sum of copies of S_{2} and 0 has an even rank we deduce that any A ∈ A_{n}(𝔽) has even rank.

The following result is known to the experts. We bring its proof for completeness.

Proposition 5.2. Let 𝔽 = ℂ, ℝ, n ≥ 2, p ≥ 1 be integers and assume that p ≤ ⌊\frac{n}{2}⌋. Let ℙW_{2p,n}(𝔽) ⊂ ℙA_{n}(𝔽) be the projective variety of all (nonzero) skew symmetric matrices of rank at most 2p. Then ℙW_{2p,n}(𝔽) is an irreducible projective variety in ℙA_{n}(𝔽) of codimension \binom{n−2p}{2}. The variety of its singular points is ℙW_{2(p−1),n}(𝔽).

Proof. Let W_{2p,n}^{o}(𝔽) ⊂ A_{n}(𝔽) be the quasi-variety of all n × n skew symmetric matrices of rank 2p. Proposition 5.1 yields that GL(n, 𝔽) acts transitively on W_{2p,n}^{o}(𝔽). Hence W_{2p,n}^{o}(𝔽) is a homogeneous space and a manifold. Since W_{2(p−1),n}(𝔽) is a strict affine subvariety of W_{2p,n}(𝔽) it follows that W_{2p,n}^{o}(𝔽) is a subset of smooth points and dim W_{2p,n}^{o}(𝔽) = dim W_{2p,n}(𝔽). The neighborhood of each point is obtained by the corresponding action of the neighborhood of I_{n} ∈ GL(n, 𝔽). Proposition 5.1 yields that the orbit of any B ∈ W_{2(p−1),n}(𝔽) does not contain any matrix in W_{2p,n}^{o}(𝔽). Hence W_{2(p−1),n}(𝔽) is the variety of singular points in W_{2p,n}(𝔽).

We now find the dimension and codimension of W_{2p,n}(𝔽). For p = ⌊\frac{n}{2}⌋, we have W_{2p,n}(𝔽) = A_{n}(𝔽). Hence dim W_{2⌊ \frac{n}{2} ⌋,n}(𝔽) = \binom{n}{2} and codim W_{2⌊ \frac{n}{2} ⌋,n}(𝔽) =

\binom{n−2⌊ \frac{n}{2} ⌋}{2} = 0. Let 1 ≤ p < ⌊\frac{n}{2}⌋. Let A = (a_{ij})_{i,j=1}^{n} ∈ W_{2p,n}^{o}(𝔽). Then A has 2p independent rows. Assume for simplicity that the first 2p rows are linearly independent. Hence the first 2p columns of A are linearly independent. Hence A_{1} = (a_{ij})_{i,j=1}^{2p} ∈ A_{2p}(𝔽) is nonsingular. Therefore there exists a unique block lower

triangular matrix T = ( \begin{matrix}I_{2p} & 0 \\ R & I_{n−2p} \end{matrix} ) such that T AT^{⊤} = A_{1} ⊕ 0. Equivalently A =

T^{−1}(A_{1}⊕0)(T^{⊤})^{−1}. Hence dim W_{2p,n} = \binom{2p}{2}+2p(n−2p) and codim W_{2p,n} = \binom{n−2p}{2}. Thus, codim ℙW_{2p,n} = \binom{n−2p}{2}.

Theorem 5.3. Let 𝔽 = ℝ, ℂ and 4 ≤ n, 1 ≤ p < ⌊\frac{n}{2}⌋. Let ℙW_{2p,n}(𝔽) be the irreducible variety of all (projectivized) nonzero skew symmetric n × n matrices of rank at most 2p in the projective space ℙA_{n}(𝔽) of all nonzero n × n skew symmetric matrices over 𝔽. Then the degree of ℙW_{2p,n}(ℂ) is odd if and only if either p or n − p is divisible by 2^{⌈log_{2}(n−2p)⌉}. Furthermore, if either p or n − p is divisible by 2^{⌈log_{2}(n−2p)⌉}, then any (\binom{n−p}{2} + 1)-dimensional subspace of n×n real skew symmetric matrices contains a nonzero matrix of rank at most 2p. For these values of n and p the dimensions of subspaces are best possible, i.e., (1.6) holds.

Proof. Recall from (1.3) that ε_{2p,n} := deg ℙW_{2p,n} = δ_{2p+1,n}/2^{n−2p−1}. The definition (2.1) of θ_{q,n} yields that ν_{2}(ε_{2p,n}) = ν_{2}(θ_{n−2p−1,n}) − (n − 2p − 1). Proposition 2.1 yields that ν_{2}(ε_{2p,n}) = ν_{2}(θ_{n−2p,n}). Use Theorem 3.1 to deduce that ε_{2p,n} is odd if and only if either p or n − p is divisible by 2^{⌈log_{2}(n−2p)⌉}.

Assume that either p or n − p is divisible by 2^{⌈log_{2}(n−2p)⌉}. Then the discussion in §1 implies that any (\binom{n−p}{2} + 1)-dimensional subspace of n × n real skew symmetric matrices contains a nonzero matrix of rank at most 2p. The sharpness of these dimensions follows from the fact that a complex subspace L of A_{n}(ℂ) of dimension \binom{n−p}{2} in general position will not contain a nonzero A ∈ A_{n}(ℂ) of rank at most 2p.

Corollary 5.4. Let n ≡ 2 (mod 4). Then any two-dimensional real subspace of n × n skew symmetric matrices contains a nonzero singular matrix.

6 Rectangular matrices and the parity of γ_{k,m,n}

In this section we consider the parity problem for γ_{k,m,n}, the latter being defined in (1.2). It is more convenient to introduce the following symmetric quantity. For n ∈ ℕ, let H(n) be the hyperfactorial ∏_{k=0}^{n−1} k!. Let a, b, c ∈ ℕ. Then a straightforward calculation shows:

B(a, b, c) = ∏_{i=1}^{a} ∏_{j=1}^{b} ∏_{k=1}^{c} \frac{(i + j + k − 1)}{(i + j + k − 2)}

= ∏_{i=1}^{a} \frac{(b + c + i − 1)! (i − 1)!}{(b + i − 1)! (c + i − 1)!}

= \frac{H(a) H(b) H(c) H(a + b + c)}{H(a + b) H(b + c) H(c + a)}.  (6.1)

B(a, b, c) is a symmetric function on ℕ^{3}. We remark that B(a, b, c) is the number of plane partitions which are contained in an a × b × c box (see e.g. [4]). From the definition (1.2) of γ_{k,m,n} it is obvious that

γ_{k,m,n} = B(n − k, m − k, k), 1 ≤ k ≤ min(m, n).  (6.2)

For simplicity of notation we let

S(a) := ∑_{i=0}^{a−1} s(i) and ν(a, b, c) := ν_{2}(B(a, b, c)) for any a, b, c ∈ ℕ.

Then, by Proposition 2.3, we have ν_{2}(H(a)) = \frac{(a−1)a}{2} − S(a) and

ν(a, b, c) = −S(a + b + c) − S(a) − S(b) − S(c) + S(a + b) + S(b + c) + S(a + c). (6.3)

Lemma 6.1. Let a, b, c ∈ ℕ. Then the following identities hold:

ν(2a, 2b, 2c) = 2ν(a, b, c),  (6.4)
ν(2a, 2b + 1, 2c + 1) = ν(a, b + 1, c) + ν(a, b, c + 1),  (6.5)
ν(2a + 1, 2b, 2c) = ν(a, b, c) + ν(a + 1, b, c),  (6.6)

ν(2a + 1, 2b + 1, 2c + 1) = ν(a, b + 1, c + 1) + ν(a + 1, b, c)
+ s(b + c) − s(b + c + 1) + 2.  (6.7)

In particular,

(1) B(2a, 2b, 2c) is odd if and only if B(a, b, c) is odd.

(2) B(2a, 2b + 1, 2c + 1) is odd if and only if both B(a, b + 1, c) and B(a, b, c + 1) are odd.

(3) B(2a + 1, 2b, 2c) is odd if and only if both B(a, b, c) and B(a + 1, b, c) are odd.

(4) B(2a + 1, 2b + 1, 2c + 1) is always even.

Proof. Equality (2.8) is equivalent to

S(2p) = 2S(p) + p, S(2p + 1) = S(p + 1) + S(p) + p, for any p ∈ ℕ. (6.8)

Use (6.3) and the above equalities to deduce (6.4)–(6.6) straightforwardly. In particular, these equalities yield the corresponding claims about the oddness of B(u, v, w).

To obtain (6.7), we use in addition to (6.3) and the above equalities the obvious equality S(p + 1) = S(p) + s(p) for p = b + c, b + c + 1. Since s(p + 1) ≤ s(p) + 1 it follows that B(2a + 1, 2b + 1, 2c + 1) is always even.

Remark 6.2. (1) Lemma 6.1 provides us with an algorithm to compute the parity of B(a, b, c) from the binary expansions of a, b, c directly, without having to actually compute B(a, b, c). Namely, given a, b, c, one determines the parities of a, b, c. If all of a, b, c are odd, then Conclusion (4) in Lemma 6.1 says that B(a, b, c) is even. If all of a, b, c are even, then one uses Conclusion (1) to reduce the problem to the problem of determining the parity of B(a/2, b/2, c/2). If exactly two of a, b, c should be odd, then one uses Conclusion (2) for a similar reduction, and if only one of a, b, c is odd, then one uses Conclusion (3). One sees quickly that this yields an algorithm which can be most conveniently run on the binary expansions of a, b, c. See Proposition 6.5 for an attempt to turn this algorithm into a concrete characterization of those a, b, c for which B(a, b, c) is odd.

(2) For the interested reader, we remark that the inspiration for Lemma 6.1 comes from results on plane partitions due to Stembridge and Eisenkölbl. More precisely, Stembridge showed in [20] that a certain (−1)-enumeration (for our purposes it suffices to say that this means a weighted enumeration in which some plane partitions count as 1, as in ordinary enumeration, and others count as −1) of plane partitions contained in an a × b × c-box is equal (up to sign) to the number of self-complementary plane partitions contained in the same box. Since, by definition of self-complementary plane partitions, there cannot exist any if all of a, b, c are odd, this result implies immediately Conclusion (4) in Lemma 6.1. Subsequently, Eisenkölbl [5] has embarked on the (−1)-enumeration of self-complementary plane partitions. Her result is that a certain (−1)-enumeration of self-complementary plane partitions contained in an a × b × c-box is equal to

B (\frac{a}{2}, \frac{b}{2}, \frac{c}{2})^{2} for a, b, c even,
B (\frac{a}{2}, \frac{b+1}{2}, \frac{c−1}{2}) B (\frac{a}{2}, \frac{b−1}{2}, \frac{c+1}{2}) for a even and b, c odd,

B (\frac{a+1}{2}, \frac{b}{2}, \frac{c}{2}) B (\frac{a−1}{2}, \frac{b}{2}, \frac{c}{2}) for a odd and b, c even.

The first of the three cases implies Conclusion (1) in Lemma 6.1, the second implies Conclusion (2), and the third implies Conclusion (3). The relations (6.4)–(6.7) refine these conclusions on the level of 2-adic valuations.

Let b and c be two nonnegative integers. Furthermore, let

b = ∑_{i=0}^{∞} b_{i}2^{i}, c = ∑_{i=0}^{∞} c_{i}2^{i}, b_{i}, c_{i} ∈ {0, 1}, i = 0, …,

be the binary expansion of b and c, respectively. We say that the pair (b, c) has a disjoint binary expansion if b_{i}c_{i} = 0 for i = 0, . . .. The following proposition is straightforward to establish.

Proposition 6.3. Let b and c be nonnegative integers. Then s(b + c) ≤ s(b) + s(c), and s(b + c) = s(b) + s(c) if and only the pair (b, c) has a disjoint binary expansion.

To find out under which conditions on the parameters a, b, c the number B(a, b, c) is odd, it is enough to consider the case a ≤ min(b, c).

Theorem 6.4. Let b, c ∈ ℕ. Then

1. B(1, b, c) is odd if and only if (b, c) has a disjoint binary expansion. In particular, for any q ≥ 0, B(2^{q}, 2^{q}b, 2^{q}c) is odd if and only if (2^{q}b, 2^{q}c) has a disjoint binary expansion.

2. Let min(b, c) ≥ 2.

• If b and c are even then B(2, b, c) is odd if and only if the pair (b, c) has a disjoint binary expansion.

• If b is even and c is odd then B(2, b, c) is odd if and only if the pairs (b, c) and (b, c + 1) have disjoint binary expansions.

• If b and c are odd then B(2, b, c) is odd if and only if the pairs (b, c + 1) and (b + 1, c) have disjoint binary expansions.

3. Let min(b, c) ≥ 3.

• Assume that b and c are even.

If b, c ≡ 0 mod 4 then B(3, b, c) is odd if and only if the pair (b, c) has a disjoint binary expansion. If b, c + 2 ≡ 0 mod 4 then B(3, b, c) is odd if and only if the pairs (b, c) and (b, c + 2) have disjoint binary expansions. If b, c ≡ 2 mod 4 then B(3, b, c) is odd if and only if the pairs (b, c), (b, c + 2) and (b + 2, c) have disjoint binary expansions.

• Assume that b is even and c is odd.

If b ≡ 0 mod 4 then B(3, b, c) is odd if and only if the pairs (b, c) and (b, c + 1) have disjoint binary expansions. If b ≡ 2 mod 4 then B(3, b, c) is odd if and only if the pairs (b, c + 1) and (b + 2, c) have disjoint binary expansions.

Proof. 1. The expression (6.1) yields that B(1, b, c) = \binom{b+c}{b}. Hence ν(1, b, c) = s(b)+s(c)−s(b+c). Thus ν(1, b, c) = 0 if and only if (b, c) has a disjoint binary expansion. The last assertion follows from (6.4) and from the observation that (b, c) has a disjoint binary expansion if and only if (2^{q}b, 2^{q}c) has a disjoint binary expansion.

2. • If b and c are even then Conclusion (1) in Lemma 6.1 and item 1, which we just established, yield that B(2, b, c) is odd if and only the pair (b, c) has a disjoint binary expansion.

• Assume that b = 2b′, c = 2c′ + 1, b′, c′ ∈ ℕ. Since ν(a, b, c) is a symmetric function in a, b, c, (6.6) yields that ν(2, 2b′, 2c′ + 1) = ν(1, b′, c′) + ν(1, b′, c′ + 1). Hence B(2, b, c) is odd if and only if (b′, c′) and (b′, c′ + 1) have disjoint binary expansions. This is equivalent to the assumption that the two even pairs (b, c − 1) and (b, c + 1) have disjoint binary expansions. Since b is even and c odd the assumption that (b, c − 1) has disjoint binary expansions is equivalent to the assumption that (b, c) has a disjoint binary expansion.

• Assume that b = 2b′ + 1, c = 2c′ + 1, b′, c′ ∈ ℕ. Then (6.5) yields ν(2, b, c) = ν(1, b′ + 1, c) + ν(1, b′, c′ + 1). Hence B(2, b, c) is odd if and only if (b′ + 1, c′) and (b′, c′ + 1) have disjoint binary expansions. This is equivalent to the assumption that the two even pairs (b + 1, c − 1) and (b − 1, c + 1) have disjoint binary expansions. This is also equivalent to to the assumption that (b + 1, c) and (b, c + 1) have disjoint binary expansions.

3. • Assume that b = 2b′, c = 2c′, a′, b′ ≥ 2. Relation (6.6) implies that B(3, b, c) = B(1, b′, c′) + B(2, b′, c′). Hence B(3, b, c) is odd if an only if B(1, b′, c′) and B(2, b′, c′) are odd. Recall that B(1, b′, c′) is odd if and only if (b′, c′) has a disjoint binary expansion. This is equivalent to the assumption that (b, c) has a disjoint binary expansion. Assume that b′ and c′ are even. Then B(2, a′, b′) is odd if and only (b′, c′) has a disjoint binary expansion. Assume now that b′ is even and c′ are is odd. Then B(2, b′, c′) is odd if (b′, c′) and (b′, c′ + 1) have disjoint binary expansions. This is equivalent to the assumption that (b, c) and (b, c+2) have disjoint binary expansions. Assume now that b′ and c′ is odd. Then B(2, b′, c′) is odd if and only if the pairs (b′, c′ + 1) and (b′ + 1, c′) have disjoint binary expansions. This is equivalent to the assumption that the pairs (b, c+2) and (b+2, c) have disjoint binary expansions.

• Assume that b = 2b′, c = 2c′ + 1, b′ ≥ 2, c′ ≥ 1. Then ν(3, 2b′, 2c′ + 1) = ν(1, b′, c′ + 1) + ν(2, b′, c′). Hence B(3, b, c) is odd if and only if B(1, b′, c′ + 1) and B(2, b′, c′) are odd. B(1, b′, c′ + 1) is odd if and only if (b′, c′ + 1) has a disjoint binary expansion. This is equivalent to the assumption that (b, c + 1) has a disjoint binary expansion. Assume that b′ is even, i.e., 4 | b. Suppose first that c′ is even, i.e., 4 | (c − 1). Then B(2, b′, c′) is odd if and only if (b′, c′) has a disjoint binary expansion. This is equivalent to the assumption that (b, c) has a disjoint binary expansion.

Assume second that c′ is odd, i.e., 4 | (c + 1). Then B(2, b′, c′) is odd if and only if (b′, c′) and (b′, c′ + 1) have disjoint binary expansions. This is equivalent to the assumption that (b, c) and (b, c+1) have disjoint binary expansions. Assume now that b′ is odd, i.e., 4 | (b + 2). Suppose first that c′ is even. Then B(2, b′, c′) is odd if and only if (b′, c′) and (b′ + 1, c′) have disjoint binary expansions. This is equivalent to the assumption that (b, c) and (b + 2, c) have disjoint binary expansions. Suppose second that c′ is odd. Assume first that c′ = 1, i.e., c = 3. Then B(2, b′, 1) is odd if and only if (b′, 2) has a disjoint binary expansion. This is equivalent to the assumption that (b, 4) = (b, c + 1) has a disjoint binary expansion. Since 4 | (b + 2) it follows that (b + 2, 3) has a disjoint binary expansion. Assume second that c′ ≥ 3. Then B(2, b′, c′) is odd if and only if (b′+1, c′) and (b′, c′ + 1) have disjoint binary expansions. This is equivalent to the assumption that (b + 2, c) and (b, c + 1) have disjoint binary expansions.

The above theorem can be generalized schematically as follows:

Proposition 6.5. Let a, b, c ∈ ℕ and assume that min(b, c) ≥ a. Let q := ⌈log_{2} a⌉ and assume that b ≡ b_{r}, c ≡ c_{r} mod 2^{q} for some b_{r}, c_{r} ∈ [0, 2^{q} − 1]. Then there exists a sequence of nonnegative integers d_{i}, e_{i} ∈ [0, 2^{q} − 1], i = 1, …, N(a, b_{r}, c_{r}), depending only on a, b_{r}, c_{r}, such that B(a, b, c) is odd if and only (b + d_{i}, c + e_{i}) has a disjoint binary expansion for i = 1, …, N(a, b_{r}, c_{r}).

Proof. We prove the proposition by induction on q. For q = 0, 1 the proposition holds in view of Theorem 6.4. Assume that the proposition holds for any q ≤ p − 1, where p ≥ 2 and any b, c such that min(b, c) ≥ a. Assume that ⌈log_{2} a⌉ = p.

• Let a = 2a′, a′ ∈ ℕ. Then ⌈log_{2} a⌉ = ⌈log_{2} a′⌉ + 1. Assume first that b and c are even. Then ν(a, b, c) = 2ν(\frac{a}{2}, \frac{b}{2}, \frac{c}{2}) and the proposition follows straightforwardly from the induction hypothesis.

Assume now that b = 2b′, c = 2c′ +1, a′ ≤ b′, c′ ∈ ℕ. Then ν(2a′, 2b′, 2c′ +1) = ν(a′, b′, c′) + ν(a′, b′, c′ + 1). Hence B(a, b, c) is odd if and only B(a′, b′, c′) and B(a′, b′, c′ +1) are odd. Use the induction hypothesis and the observation that (u, v) has a disjoint binary expansion if and only if (2u, 2v + 1) has one for the case B(a′, b′, c′) to deduce the proposition. (For the case B(a′, b′, c′ + 1) note that if d_{i} ≤ 2^{p−1} − 1 then 2d_{i} + 1 ≤ 2^{p} − 1.)

Use the equality B(a, b, c) = B(a, c, b) to deduce the proposition in the case that b is odd and c is even.

Assume now that b = 2b′ + 1, c = 2c′ + 1, a′ ≤ b′, c′ ∈ ℕ. Then ν(2a′, 2b′ + 1, 2c′ + 1) = ν(a′, b′ + 1, c′) + ν(a′, b′, c′ + 1). Hence B(a, b, c) is odd if and only B(a′, b′ + 1, c′) and B(a′, b′, c′ + 1) are odd. Use the induction hypothesis and the above remarks to deduce the proposition in this case.

• Assume that a = 2a′+1, a′ ∈ ℕ. Then ⌈log_{2} a⌉ = ⌈log_{2} a+1⌉ = ⌈log_{2} a′+1⌉+1.

Since B(a, b, c) = B(a, c, b) is even if a, b, c are odd, it is enough to consider the case b = 2b′, a′ < b′ ∈ ℕ. Assume first that c = 2c′, a′ < c′ ∈ ℕ. Then ν(2a′ + 1, 2b′, 2c′) = ν(a′, b′, c′) + ν(a′ + 1, b′, c′). Hence B(a, b, c) is odd if and only B(a′, b′, c′) and B(a′ +1, b′, c′) are odd. Use the induction hypothesis and the above arguments to deduce the proposition.

Assume finally that c = 2c′ + 1, a′ ≤ c′. Then ν(2a′ + 1, 2b′, 2c′ + 1) = ν(a′, b′, c′+1)+ν(a′+1, b′, c′). Hence B(a, b, c) is odd if and only B(a′, b′, c′+1) and B(a′ + 1, b′, c′) are odd. The case where B(a′, b′, c′ + 1) is odd is done by induction on a′. For c′ > a′ the case B(a′ + 1, b′c′) is odd is done by induction on a′ + 1. The case c′ = a′, which is equivalent to the case where B(a′ + 1, b′, a′) = B(a′, b′, a′ + 1) is odd is done by induction on a′. (As in the case of B(3, 2b′, 3) in Theorem 6.4.)

In principle the proof of Proposition 6.5 can be used to find the sequences d_{i}, c_{i}, i = 1, …, N(a, b_{r}, c_{r}), recursively. However, the explicit construction of all such sequences seems complicated even in the simple case where a = 2^{q}, q = 2, . . .. Note that Case 1 of Theorem 6.4 finds the sequence for a = 2^{q} and b_{r} = c_{r} = 0. The cases b_{r} = 0, c_{r} = 1 and b_{r} = c_{r} = 1 have simple results.

Proposition 6.6. Let q ∈ ℕ and 2^{q} ≤ b, c ∈ ℕ. If 2^{q} | b, 2^{q} | (c − 1), then B(2^{q}, b, c) is odd if and only if (b, c) and (b, c+2^{q}−1) have disjoint binary expansions. If 2^{q} | (b − 1), 2^{q} | (c − 1), then B(2^{q}, b, c) is odd if and only if (b + 1, c), (b, c + 1), (b + 2^{q} − 1, c), and (b, c + 2^{q} − 1) have disjoint binary expansions.

The proof of this proposition is left to the reader. The results of §1 yield the following theorem.

Theorem 6.7. Let k, m, n ∈ ℕ, assume that k < min(m, n), and let γ_{k,m,n} be the positive integer given by (1.2). Let M_{m,n}(ℝ) be the space of all m × n real valued matrices. Let L ⊂ M_{m,n}(ℝ) be a subspace of dimension (m − k)(n − k) + 1. If γ_{k,m,n} is odd then L contains a nonzero matrix rank at most k.

Corollary 6.8. For the following positive integers 1 ≤ k < n ≤ m any ((m − k)(n − k) + 1)-dimensional subspace of M_{m,n}(ℝ) contains a nonzero matrix rank at most k:

1. k = n − 1 and (m − n + 1, n − 1) has a disjoint binary expansion.

2. 2 ≤ k = n − 2.

• n and m are even and (n − 2, m − n + 2) has a disjoint binary expansion.

• n is even, m is odd, (n−2, m−n+2) and (n−2, m−n+3) have disjoint binary expansions.

• n is odd, m is even, (n−2, m−n+3) and (n−1, m−n+2) have disjoint binary expansions.

3. 3 ≤ k = n − 3.

• 4 | (n − 3), 4 | m, and (n − 3, m − n + 3) has a disjoint binary expansion.

• 4 | (n − 3), 4 | (m + 2), (n − 3, m − n + 3) and (n − 3, m − n + 5) have disjoint binary expansions.

• 4 | (n − 1), 4 | (m + 2), (n − 3, m − n + 3) and (n − 1, m − n + 3) have disjoint binary expansions.

• 4 | (n − 1), 4 | m, (n − 1, m − n + 3) and (n − 3, m − n + 5) have disjoint binary expansions.

• 4 | (n − 3), m odd, (n − 3, m − n + 3) and (n − 3, m − n + 4) have disjoint binary expansions.

• 4 | (n − 1), m odd, (n − 3, m − n + 4) and (n − 1, m − n + 3) have disjoint binary expansions.

• 4 | (m − n + 3), n is even, (n − 3, m − n + 3) and (n − 2, m − n + 3) have disjoint binary expansions.

• 4 | (m − n + 5), n is even, (n − 2, m − n + 3) and (n − 3, m − n + 5) have disjoint binary expansions.

4. Let q ∈ ℕ.

• n = k + 2^{q}, 2^{q} | k, 2^{q} | m, and (k, m − k) has a disjoint binary expansion.

• n = k + 2^{q}, 2^{q} | k, 2^{q} | (m − 1), (k, m − k) and (k, m − k + 2^{q} − 1) have disjoint binary expansions.

• 2^{q+1} < n = k+2^{q}, 2^{q} | (k−1), 2^{q} | (m−1), (k, m−k) and (k+2^{q}−1, m−k) have disjoint binary expansions.

• 2^{q+1} < n = k + 2^{q}, 2^{q} | (k − 1), 2^{q} | (m − 2), and the pairs (k + 1, m − k), (k, m − k + 1), (k + 2^{q} − 1, m − k), and (k, m − k + 2^{q} − 1) have disjoint binary expansions.

References

[1] J.F. Adams, Vector fields on spheres, Annals of Math. 75 (1962), 603–632.

[2] E. Arbarello, M. Cornalba, P.A. Griffiths and J. Harris, Geometry of Algebraic Curves, I, Grundlehren der math. Wissenschaften, vol. 267, Springer, 1985.

[3] M.A. Berger and S. Friedland, The generalized Radon–Hurwitz numbers, Compositio Mathematica 59 (1986), 113–146.

[4] D.M. Bressoud, Proofs and confirmations: The story of the alternating sign matrix conjecture, Cambridge University Press, Cambridge, 1999.

[5] T. Eisenkölbl, (−1)-enumeration of self-complementary plane partitions, Electron. J. Combin. 12(1) (2005), Article #R7, 22 pp.

[6] D. Falikman, S. Friedland and R. Loewy, On spaces of matrices containing a nonzero matrix of bounded rank, Pacific J. Math. 207 (2002), 157–176.

[7] S. Friedland and A. Libgober, Generalizations of the odd degree theorem and applications, Israel J. Math. 136 (2003), 353–371.

[8] S. Friedland, J.W. Robbin and J.H. Sylvester, On the crossing rule, Comm. on Pure and Appl. Math. 37 (1984), 19–37.

[9] F.R. Gantmacher, The Theory of Matrices II, Chelsea Pub. Com., 1964.

[10] S.R. Ghorpade and C. Krattenthaler, The Hilbert series of Pfaffian rings, in: Algebra, Arithmetic and Geometry with Applications (C. Christensen, G. Sundaram, A. Sathaye and C. Bajaj, eds.) Springer–Verlag, New York, 2004, pp. 337–356.

[11] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics, Addison Wesley, Reading, Massachusetts, 1989.

[12] J. Harris and L.W. Tu, On symmetric and skew-symmetric determinantal varieties, Topology 23 (1984), 71–84.

[13] J. Harris and L.W. Tu, Chern numbers of kernels and cokernel bundles, Invent. Math. 75 (1984), 467–475.

[14] A. Hurwitz, Über die Komposition der quadratischen Formen, Math. Ann. 88 (1922), 1–25.

[15] R.C. King and N.G.I. El-Sharkaway, Standard Young tableaux and weight multiplicities of the classical Lie groups, J. Physics A 16 (1983), 3153–3178.

[16] P.D. Lax, The multiplicity of eigenvalues, Bull. Amer. Math. Soc. 6 (1982), 213–215.

[17] A.M. Legendre, Théorie des Nombres, Firmin Didot Frères, Paris, 1830.

[18] J. Radon, Lineare Scharen orthogonaler Matrizen, Abh. Math. Sem. Univ. Hamburg 1 (1923), 1–14.

[19] J.W. Milnor and J.D. Stasheff, Characteristic Classes, Annals of Math. Studies 76, Princeton Univ. Press, 1974.

[20] J.R. Stembridge, Some hidden relations involving the ten symmetry classes of plane partitions, J. Combin. Theory Ser. A 68 (1994), 372–409.

[21] S. Sundaram, Tableaux in the representation theory of the classical Lie groups, in: Invariant Theory and Tableaux (Dennis Stanton, ed.), Springer–Verlag, 1990, pp. 191–225.