# Original formulation of Spira's Lemma

I'm currently reading the book "Proof Complexity" by Jan Krajíček (2019), where Spira's Lemma is mentioned:

Let $$T$$ be a finite $$k$$-ary tree and $$|T| > 1$$. Then there is a node $$a \in T$$ such that $$(1 / (k + 1))|T| \leq |T_a|, |T^a| \leq (k/(k+1))|T|$$ (where $$|T|$$ denotes the number of leaves of the tree $$T$$).

I came across the lemma various times during my studies of proof complexity, but I was never able to find the original paper in which it was established:

On time hardware complexity tradeoffs for Boolean functions, by P. M. Spira. Fourth Hawaii International Symp. on Systems Sci., 1971, pp. 525-527.

Does anybody know where I can find it?

Thank you very much!

• what are $T_a$ and $T^a$? Mar 4 at 14:26
• Apparently, it’s actually Fourth Hawaii International Conference on System Sciences, cf. books.google.cz/books/about/… . But I do not know how to get hold of it short of finding a physical copy in a library. Mar 4 at 14:27
• @mathworker21 Since this is Spira’s lemma, one of those must be the subtree of $T$ rooted at $a$, and the other one whatever is left of $T$ after removing the subtree (possibly leaving $a$ itself in place). The lower and upper bounds apply to both. Mar 4 at 14:31
• To add to Emil's answer, hicss.hawaii.edu/resources/proceedings seems to contain information to help you locate a physical copy. It seems IEEE has not indexed proceedings before 1988 (ieeexplore.ieee.org/xpl/conhome/1000730/all-proceedings). If your institutions has some form of IEEE subscription, it might be useful to mention it when you contact the relevant people. Mar 4 at 16:19
• UCSD and Oxford and McGill and Hamburg and a few other libraries have a copy, see here Mar 5 at 1:35