%I
%S 1,2,2,4,5,6,8,9,10,16,17
%N a(n) is the maximal size of a set S of points in {0,1}^n in real ndimensional Euclidean space such that every angle determined by three points in S is acute.
%C Consider the 2^n points {0,1}^n in real Euclidean space. Then a(n) = maximal size of a subset S of these 2^n points such that there is no triple of points P,Q,R in S which subtends a right angle. That is, we are not allowed to have PQ perpendicular to RQ.
%C There is an existence proof due to Erdős and Füredi that exponentially large subsets S exist: see for example Theorem 2.3 of Noga Alon's survey "Probabilistic Methods in Extremal Finite Set Theory". This was improved by Bevan and later by Ackerman and BenZwi.
%C As explained by ErdősFuredi, these sets of points are equivalent to set systems none of which is sandwiched between the intersection and the union of two others. In turn these are equivalent to socalled (2,1)separating systems. As far as I know the best construction is the one in my Israel J. Math. 2013 paper. It uses algebraic geometry and coding techniques, and it implies a lower bound on a(n) of roughly 11^{3n/50}. This is better than ErdősFuredi, Bevan, or AckermanBenZwi, which are all about (4/3)^{n/2}. It is remarkable that this construction beats the probabilistic method (and note that it implies that for large n, naive computer search will have exponentially small chance to find optimal configurations). I should also add that ErdősFuredi claimed (without proof) a lower bound of 2^{n/4} which, if correct, would be even better (but also nonconstructive).  Hugues Randriambololona, Apr 08 2016
%C For a(10)=17 a combinatorial search algorithm shows that a cubic acute 10set with 18 vertices is not possible. For a complete enumeration of sets with maximal size, see A289972.  _Fausto A. C. Cariboni_, Jul 17 2017
%C The best known lower bounds for a(1115) are 24, 32, 33, 64 and 128. a(1114) were found by D. Kamenetsky, while a(15) was found by D. Kamenetsky and V. Chubenko (see attached file). Lower bounds for n > 15 have been found by V. Harangi (see Table 3 in his paper).  _Dmitry Kamenetsky_, May 18 2018 and Jun 05 2018
%H Eyal Ackerman and Oren BenZwi, <a href="https://doi.org/10.1016/j.ejc.2008.07.020">On sets of points that determine only acute angles</a>, European Journal of Combinatorics 30 (2009) 908910.
%H N. Alon, <a href="http://www.cs.tau.ac.il/~nogaa/PDFS/set3.pdf">Probabilistic Methods in Extremal Finite Set Theory</a>
%H D. Bevan, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1r12">Sets of Points Determining Only Acute Angles and Some Related Coloring Problems</a>, Electronic J. of Combinatorics, 13(1), 2006, #R12.
%H L. Danzer and B. Grünbaum, <a href="http://dx.doi.org/10.1007/BF01193107">Uber zwei Probleme bezüglich konvexer Körper von P. Erdős und von K. L. Klee</a>, Math. Zeitschrift 79 (1962) 9599.
%H P. Erdős and Z. Füredi, <a href="http://dx.doi.org/10.1016/S03040208(08)73398X">The greatest angle among n points in the ddimensional Euclidean space</a>, Annals of Discrete Math. 17 (1983) 275283.
%H Viktor Harangi, <a href="https://users.renyi.hu/~harangi/papers/acute.pdf">Acute Sets In Euclidean Spaces</a>, Journal on Discrete Mathematics, volume 25, issue 3, (2011) 12121229.
%H Dmitry Kamenetsky, <a href="/A089676/a089676_1.txt">Lower bounds and their solutions for a(1115)</a>
%H Math StackExchange, <a href="https://math.stackexchange.com/questions/2363546/tightacutesets">Tight Acute Sets</a>
%H Hugues Randriambololona, <a href="https://doi.org/10.1007/s1185601201269">(2,1)Separating systems beyond the probabilistic bound</a>, Israel Journal of Mathematics, 195 (2013), 171186; DOI: 10.1007/s1185601201269.
%H Hugues Randriambololona, <a href="https://arxiv.org/abs/1010.5764">(2,1)Separating systems beyond the probabilistic bound</a>, arXiv:1010.5764 [math.CO], 20102012.
%F If k <= m <= n, a(k+2m) >= a(k)a(m), a(k+2m+3n) >= a(k)a(m)a(n).
%F a(n) >= 2*floor((sqrt(6)/9)(2/sqrt(3))^n), which is approximately 0.544*1.155^n.
%e a(3) = 4: {000, 011, 101, 110}.
%e a(4) = 5: {0011, 0101, 0110, 1000, 1111}.
%e The following sets are given by Bevan (2006), who also shows they are optimal:
%e a(5) = 6:
%e 0 0 0 0 0
%e 0 0 0 1 1
%e 0 0 1 0 1
%e 0 1 0 0 1
%e 1 0 0 0 1
%e 1 1 1 1 0
%e a(6) = 8:
%e 0 0 0 0 0 0
%e 0 0 0 1 1 1
%e 0 1 1 0 0 1
%e 0 1 1 1 1 0
%e 1 0 1 0 1 0
%e 1 0 1 1 0 1
%e 1 1 0 0 1 1
%e 1 1 0 1 0 0
%e a(7) = 9:
%e 0 0 0 0 0 0 0
%e 0 0 0 0 0 1 1
%e 0 0 0 1 1 0 1
%e 0 1 1 0 0 0 1
%e 0 1 1 1 1 1 0
%e 1 0 1 0 1 0 1
%e 1 0 1 1 0 1 0
%e 1 1 0 0 1 1 0
%e 1 1 0 1 0 0 1
%e a(8) = 10:
%e 0 0 0 0 0 0 0 0
%e 0 0 0 0 0 0 1 1
%e 0 0 0 0 0 1 0 1
%e 0 0 0 1 1 0 0 1
%e 0 1 1 0 0 0 0 1
%e 0 1 1 1 1 1 1 0
%e 1 0 1 0 1 0 0 1
%e 1 0 1 1 0 1 1 0
%e 1 1 0 0 1 1 1 0
%e 1 1 0 1 0 0 0 1
%e For a(9) = 16 Bevan uses the construction in his Theorem 4.2, which shows that a(3k) >= a(k)^2 for all k, and then a computer search shows that this is optimal for k = 3. Let v0,v1,v2,v3 denote the four vectors for a(3). Then to get a(9)=16 use the vectors { v_i v_j v_{ji mod 4}, 0 <= i,j <= 3 }.  _N. J. A. Sloane_, Mar 30 2016
%e a(10) = 17, from Hugues Randriambololona, Apr 08 2016:
%e 0 0 0 0 0 0 0 0 0 0
%e 0 0 0 0 1 1 0 1 1 1
%e 1 1 1 0 1 1 1 0 0 1
%e 0 0 1 0 0 1 1 1 0 1
%e 1 1 0 0 0 1 0 1 0 1
%e 1 1 0 0 1 0 1 1 1 1
%e 0 1 0 1 1 0 0 1 0 0
%e 1 1 1 0 0 0 0 0 1 1
%e 1 0 0 1 1 1 1 0 1 1
%e 1 0 1 0 1 1 0 0 1 0
%e 0 1 0 1 0 1 1 0 0 0
%e 1 0 0 0 0 1 1 1 1 0
%e 1 0 1 0 1 0 1 1 0 0
%e 1 0 1 1 0 0 1 1 1 1
%e 1 1 1 1 0 1 0 1 1 0
%e 0 1 1 0 1 1 1 1 1 0
%e 1 0 1 1 1 1 0 1 0 1
%e a(11) >= 23, from _Dmitry Kamenetsky_, Jan 05 2018:
%e 0 1 1 0 0 0 1 0 1 1 1
%e 0 0 0 0 1 0 0 0 0 0 1
%e 0 0 1 1 0 0 1 0 0 0 1
%e 0 1 1 0 1 0 1 1 1 0 0
%e 0 0 1 0 1 1 0 0 1 1 1
%e 1 1 0 1 1 0 0 0 1 1 0
%e 1 0 0 1 1 0 0 1 0 1 1
%e 1 0 0 1 0 1 1 0 1 1 0
%e 1 1 1 1 1 1 0 0 0 0 0
%e 1 0 0 1 1 1 1 1 1 0 1
%e 1 0 1 0 0 0 0 0 0 0 0
%e 1 0 0 0 0 1 0 1 1 1 1
%e 0 1 0 0 1 0 1 0 0 1 0
%e 1 1 0 0 0 0 0 0 1 0 1
%e 1 1 1 0 0 1 1 1 0 1 1
%e 1 1 0 0 0 1 1 0 0 0 0
%e 0 0 0 1 0 0 1 1 0 1 0
%e 1 0 1 1 1 1 1 0 0 1 1
%e 1 1 1 1 0 0 0 1 0 0 1
%e 0 1 1 1 0 0 0 1 1 1 0
%e 0 1 1 0 1 1 0 1 0 1 0
%e 0 0 0 0 0 1 0 1 0 0 0
%e 0 1 0 1 0 1 0 0 0 0 1
%Y Cf. A289972.
%K nonn,more,nice
%O 0,2
%A _David Bevan_, Jan 06 2004
%E Edited by _N. J. A. Sloane_, Mar 29 2016 and Apr 08 2016
%E a(10) from _Fausto A. C. Cariboni_, Jul 17 2017
