Bisecting binomial coefficients. (English) Zbl 1365.05011
Summary: In this paper, we deal with the problem of bisecting binomial coefficients. We find many (previously unknown) infinite classes of integers which admit nontrivial bisections, and a class with only trivial bisections. As a byproduct of this last construction, we show conjectures \(Q2\) and \(Q4\) of T. W. Cusick and Y. Li [ibid. 149, No. 1–3, 73–86 (2005; Zbl 1072.94023)]. We next find several bounds for the number of nontrivial bisections and further compute (using a supercomputer) the exact number of such bisections for \(n \leq 51\).
MSC:
| 05A10 | Factorials, binomial coefficients, combinatorial functions |
| 11D99 | Diophantine equations |
| 94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |
| 94A60 | Cryptography |
Citations:
Zbl 1072.94023Online Encyclopedia of Integer Sequences:
Number of 0..1 arrays x(0..n-1) of n elements with zero n-1st difference.Numbers for which there exists a nontrivial bisection of binomial coefficients as given by Theorem 12 of Ionascu et al. (2016).
References:
| [1] | D. Andrica, E.J. Ionascu, Some unexpected connections between analysis and combinatorics, 2014; D. Andrica, E.J. Ionascu, Some unexpected connections between analysis and combinatorics, 2014 · Zbl 1317.05015 |
| [2] | L. Baker, S. Wagner, Erdös-Surányi sequences and trigonometric integrals, 2015. arXiv:1506.04555; L. Baker, S. Wagner, Erdös-Surányi sequences and trigonometric integrals, 2015. arXiv:1506.04555 |
| [3] | Blachman, N. M., Noise and its Effect on Communication (1966), McGraw-Hill: McGraw-Hill New York, London |
| [4] | Buzytsky, P. L., An effective formula for the number of solutions of linear Boolean equations, SIAM J. Algebr. Discrete Methods, 3, 2, 182-186 (1982) · Zbl 0491.90071 |
| [5] | Chaimovich, M.; Freiman, G.; Galil, Z., Solving dense subset-sum problems by using analytical number theory, J. Complexity, 5, 271-282 (1989) · Zbl 0686.68030 |
| [6] | Cusick, T. W.; Li, Y., \(k\)-th order symmetric SAC Boolean functions and bisecting binomial coefficients, Discrete Appl. Math, 149, 73-86 (2005) · Zbl 1072.94023 |
| [7] | Drimbe, M. O., Generalization of representation theorem of Erdös and Surányi, Comment. Math. Prace Mat., 27, 2, 233-235 (1988) · Zbl 0674.10014 |
| [8] | Farmer, J. D.; Leth, S. C., An asymptotic formula for powers of binomial coefficients, Math. Gazette, 89, 516, 385-391 (2005) |
| [9] | R. Forré, The strict avalanche criterion: spectral properties of Boolean functions and an extended definition, in: Adv. in Cryptology -Crypto.’88, 1988, pp. 450-468; R. Forré, The strict avalanche criterion: spectral properties of Boolean functions and an extended definition, in: Adv. in Cryptology -Crypto.’88, 1988, pp. 450-468 · Zbl 0715.94018 |
| [10] | Freiman, G. A., An analytical method of analysis of linear Boolean equations, Ann. New York Acad. Sci., 337, 97-102 (1980) · Zbl 0459.05013 |
| [11] | von zur Gathen, J.; Roche, J., Polynomials with two values, Combinatorica, 17, 345-362 (1997) · Zbl 0907.68134 |
| [12] | Goetgheluck, P., Computing binomial coefficients, Amer. Math. Monthly, 94, 4, 360-365 (1987) · Zbl 0617.05004 |
| [13] | Gopalakrishnan, K.; Hoffman, D. G.; Stinson, D. R., A note on a conjecture concerning symmetric resilient functions, Inform. Process. Lett., 47, 139-143 (1993) · Zbl 0782.05002 |
| [14] | Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics: A Foundation for Computer Science (1994) · Zbl 0836.00001 |
| [15] | Granville, A., Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers, (Organic Mathematics (Burnaby, BC, 1995). Organic Mathematics (Burnaby, BC, 1995), CMS Conf. Proc., vol. 20 (1997), Amer. Math. Soc., Providence, RI), 253-276 · Zbl 0903.11005 |
| [16] | Jefferies, N., Sporadic partitions of binomial coefficients, Elec. Lett., 27, 15, 134-136 (1991) · Zbl 0739.94021 |
| [17] | Lengyel, T., On the order of lacunary sums of binomial coefficients, Integers, 3, Art. 03 (2003) · Zbl 1107.11011 |
| [18] | Matthews, K., The Diophantine equation \(x^2 - D y^2 = N, D > 0\), Expo. Math., 18, 323-331 (2000) · Zbl 0976.11016 |
| [19] | Mitchell, C., Enumerating Boolean functions of cryptographic significance, J. Cryptology, 2, 155-170 (1990) · Zbl 0705.94010 |
| [20] | Polya, G.; Szegö, G., Problems and Theorems in Analysis I: Series, Integral Calculus, Theory of Functions (1972) · Zbl 0236.00003 |
| [21] | Rogawski, J., Calculus (2008), W.H. Freeman and Company |
| [22] | Tekcan, A., The Pell equation \(x^2 - D y^2 = \pm 4\), Appl. Math. Sci., 1, 8, 363-369 (2007) · Zbl 1186.11013 |
| [23] | A.F. Webster, S.E. Tavares, On the design of \(S\); A.F. Webster, S.E. Tavares, On the design of \(S\) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
