1. Introduction
Let x be a nonnegative integer. If the binary expansion of x is
then the Hamming weight of x is
.
In [1] Tu and Deng proposed the following conjecture.
Conjecture 1: Let
![](https://www.scirp.org/html/10-1200118\54e6d802-b32c-4221-92d5-b538770e6fce.jpg)
where
. Then the cardinality
.
Based on this conjecture, Tu and Deng [1] constructed two classes of Boolean functions with many good cryptographic properties. In this paper we always use the following bijection, where
is the set of binary strings of length
except the string consisting of n copies of 1.
![](https://www.scirp.org/html/10-1200118\eadd523d-3fba-4217-8972-d0dc41618f09.jpg)
![](https://www.scirp.org/html/10-1200118\bea2e205-6335-4675-885c-a1cecd76b65e.jpg)
We use
to denote the length of a binary string
. Let
. And we use the following notation
where there are k consecutive 1 and m consecutive 0 in the string.
In [1] Tu and Deng construct an algorithm which they used it to show that the conjecture above is true when
. Cusick, Li and Stanica [2] show that Conjecture 1 is true when
. In this paper, we will consider the following conjecture, which is equivalent to Conjecture 1.
Conjecture 2: Suppose that ![](https://www.scirp.org/html/10-1200118\57082e75-a876-42d1-915a-b48781b62491.jpg)
Let
![](https://www.scirp.org/html/10-1200118\2e58c7fc-3a08-487a-96c5-ec00a190de1f.jpg)
then
.
The following lemma is easy so we omit the proof.
Lemma 1.1 Let
Then following statements are true:
1) ![](https://www.scirp.org/html/10-1200118\75a44804-f3dc-47de-81a2-8459d444c2a9.jpg)
2)
;
3) The map
is bijective.
Hence ![](https://www.scirp.org/html/10-1200118\fd20928d-9aa6-4f2f-b2ce-678a08e20d7d.jpg)
So the authors in [3] actually showed that Conjecture 2 is true when
.
According to Lemma 1.1. Deng and Yuan [4] show that Conjecture 2 is true if ![](https://www.scirp.org/html/10-1200118\f7db688a-0a5b-4b9e-84ad-b8b0be4378d5.jpg)
The outline of this paper is as follows. In Section 2 we introduce some notations. In Section 3, we consider what happen if we change some digit 1 into 0 in the strings. We get a recursive formula about
and prove a new case of the conjecture.
2. A Partition of ![](https://www.scirp.org/html/10-1200118\4c93e762-c997-4d14-a6b1-dd8524e6e40a.jpg)
The following lemma is about the relation between
and
, which is proved in [4].
Lemma 2.1 Let
![](https://www.scirp.org/html/10-1200118\27937e67-60cf-47ed-8e97-60c1131bea0c.jpg)
![](https://www.scirp.org/html/10-1200118\a8352c0d-362a-4515-b7e6-f59084f04ced.jpg)
Suppose that
where
Assume that
. Then
![](https://www.scirp.org/html/10-1200118\ad5269bd-8215-4510-8f99-8bdb8bfc3c7e.jpg)
where we set ![](https://www.scirp.org/html/10-1200118\64bbd6b1-5eb9-4ab1-8b08-8d0dbae2d903.jpg)
Let
![](https://www.scirp.org/html/10-1200118\f9622817-fabd-491a-a233-d50d809948b7.jpg)
for any
and ![](https://www.scirp.org/html/10-1200118\a2e307d7-e7e1-4628-9bde-4b772d9cc225.jpg)
Then
and ![](https://www.scirp.org/html/10-1200118\4d166f4b-24a4-4106-93e3-e2c84e59abd9.jpg)
which are disjoin unions. We define a partition on
according to Lemma 2.1.
Definition 2.1 Let
be a binary string of length n. Suppose that
and ![](https://www.scirp.org/html/10-1200118\00b8040e-b9f0-4fca-9b48-971abec96f3b.jpg)
where
Let
be a binary string. Suppose that
where
We set ![](https://www.scirp.org/html/10-1200118\0f434bc3-4c53-4831-b137-a0898787fe64.jpg)
to be the subset of
such that
if and only if the following two conditions hold i)
, if ![](https://www.scirp.org/html/10-1200118\57e7cff7-f840-4e1a-94af-0f57cb829d9b.jpg)
ii)
, if ![](https://www.scirp.org/html/10-1200118\f0b61c91-093f-4761-9520-ee43379e7821.jpg)
And we will use that notation
if
.
Definition 2.2 Let
and
be two given binary strings. For any
, we set
, if
for each
.
We say that
is free if there are two strings
and
in
such that
and
.
From Definition 2.1 and Lemma 2.1 we see that
and
where k is the number of indices such that
is free.
Example 2.1 Let
,
,
and
![](https://www.scirp.org/html/10-1200118\ed0fed90-6385-4d59-989d-37e7d282d13d.jpg)
Then
and
,
,
.
So
,
and
.
Moreover, by Definition 2.2
if and only if
,
or
. That is,
is free for
. We also have
if and only if
, ![](https://www.scirp.org/html/10-1200118\c8771149-f7d8-418c-b696-f5ba365db124.jpg)
if and only if
,
or
.
3. Main Results
If
with each
, then we say that the block of
is
. Jean-P. Flori and H. Randriam [5] give some asymptotic results when each
. In particular, they show that Conjecture 2 is true if the block of t is smaller than 3 or each
is sufficient large for a fixed length of block. We give a recursive formula to show that we can restrict our attention to the case each
is smaller than the block of
in this situation. They also conjectured that
if
.
Lemma 3.1 Let
![](https://www.scirp.org/html/10-1200118\c0414674-607a-4b99-984e-060a694e48ed.jpg)
and
![](https://www.scirp.org/html/10-1200118\24c9dd00-6002-411d-9c39-3ff16070ef18.jpg)
with
and
.
Let
for
,
![](https://www.scirp.org/html/10-1200118\46872a21-e902-4a0b-96ce-8f63ed73b88b.jpg)
and
![](https://www.scirp.org/html/10-1200118\424d71ba-d901-4e60-b119-87e7919e6ccc.jpg)
Then
![](https://www.scirp.org/html/10-1200118\a625c07c-e4b8-4eca-83b5-4bd89ea86fd2.jpg)
Proof. Note that for any
, if
, then
for each
, moreover in this case we have
.
Let
![](https://www.scirp.org/html/10-1200118\a646b9ef-0265-4876-9c23-88c0227d6cf0.jpg)
![](https://www.scirp.org/html/10-1200118\d74a1fbb-81e9-4936-a3a2-2f9255be035c.jpg)
then
. Similarly we write
where
![](https://www.scirp.org/html/10-1200118\9c655ce9-fb9e-46ab-bc1c-3bc7b8d2826f.jpg)
![](https://www.scirp.org/html/10-1200118\b2c93b40-762d-44b4-b717-27d3fdf2ffab.jpg)
We observe that if
, then
if and only if each
Now if
by comparing the number of free indices we have
.
Hence,
. If each
, then
.
Suppose that
. Then
![](https://www.scirp.org/html/10-1200118\f03614ee-b1b2-4919-9e37-23a236e1b03b.jpg)
So
![](https://www.scirp.org/html/10-1200118\22c427bc-8bb6-469c-a6a6-7a48d23a0563.jpg)
Therefore
![](https://www.scirp.org/html/10-1200118\44ddd039-c3f1-4123-a058-9e4f6379f6ee.jpg)
![](https://www.scirp.org/html/10-1200118\9c7c1a9b-c263-4326-9853-ee475f1a9f51.jpg)
This finishes the proof.
Remark 3.1 Let
with
. It is clear that
![](https://www.scirp.org/html/10-1200118\f4277a30-3e33-4147-aa8f-347729cf0f29.jpg)
for any
So we use the following notation
means that there are sufficient consecutive 0 in the string.
We set
![](https://www.scirp.org/html/10-1200118\460985ce-aff1-494d-9bd6-c2122afae99f.jpg)
for
.
Theorem 3.1 Let
,
,
,
,
,
where each
and
Then
.
Proof. Suppose that those strings have the same length and
. By Lemma 3.1
![](https://www.scirp.org/html/10-1200118\5879d030-1fd6-45cc-ac64-d073f4985bd2.jpg)
![](https://www.scirp.org/html/10-1200118\b8a1d7d2-8265-45d3-8d2d-cdf34e1d1ed6.jpg)
![](https://www.scirp.org/html/10-1200118\f408abfc-1ff0-4bf3-bdb6-2a3184f346ae.jpg)
Let
.
If
, by comparing the number of free indices we have
where
. We set
![](https://www.scirp.org/html/10-1200118\1acb3650-4f40-48be-b708-26633ab63d94.jpg)
and
.
Then
![](https://www.scirp.org/html/10-1200118\5d8900e7-797a-4dd4-b7e7-8a8504f1c9de.jpg)
Let
and
.
Now consider the following mapping
and
. If
and
then
.
Then
.
So
.
If
then
.
It is easy to see that
and
.
By the discussion above we obtain
, and
.
This finishes the proof.
Corollary 3.1 With the same notations in Theorem 3.1. Suppose that
then
.
Proof. We proof the statement by induction on
.
The case
implies that
.
This was proved in [4]. Without loss of generality we can assume that
and
. By induction
by Theorem 3.1
.
The proof is completed by induction on
.
Corollary 3.2 Let
. Then
.
Proof. By Corollary 3.1 it suffice to show that case when each
. So we have
, which is proved in [4].