<p>I'm currently reading the book &quot;Proof Complexity&quot; by Jan Krajíček (2019), where Spira's Lemma is mentioned:</p>
<blockquote>
<p>Let <span class="math-container">$T$</span> be a finite <span class="math-container">$k$</span>-ary tree and <span class="math-container">$|T| &gt; 1$</span>. Then there is a node <span class="math-container">$a \in T$</span> such that <span class="math-container">$(1 / (k + 1))|T| \leq |T_a|, |T^a| \leq (k/(k+1))|T|$</span> (where <span class="math-container">$|T|$</span> denotes the number of leaves of the tree <span class="math-container">$T$</span>).</p>
</blockquote>
<p>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:</p>
<p><strong>On time hardware complexity tradeoffs for Boolean functions, by P. M. Spira. Fourth Hawaii International Symp. on Systems Sci., 1971, pp. 525-527.</strong></p>
<p>Does anybody know where I can find it?</p>
<p>Thank you very much!</p>

CC BY-SA 4.0
2024-03-04T14:26:15.150Z
what are $T_a$ and $T^a$?
mathworker21
CC BY-SA 4.0
2024-03-04T14:27:35.047Z
Apparently, it’s actually Fourth Hawaii International *Conference* on System Sciences, cf. https://books.google.cz/books/about/Proceedings_Fourth_Hawaii_International.html?id=Y0zVjwEACAAJ . But I do not know how to get hold of it short of finding a physical copy in a library.
Emil Jeřábek
CC BY-SA 4.0
2024-03-04T14:31:26.790Z
@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.
Emil Jeřábek
CC BY-SA 4.0
2024-03-04T16:19:51.450Z
To add to Emil's answer, https://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 (https://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.
chazisop
CC BY-SA 4.0
2024-03-05T01:33:14.713Z
1. find some folks who might have a paper copy (e.g. Sam Buss) and ask them to send you a scanned copy, 2. go to one of the larger university libraries which might have a copy (University of Toronto did not), 3. use cross-University library services to ask University of Hawaii Library to scan and send you a copy.
Kaveh
CC BY-SA 4.0
2024-03-05T01:35:39.783Z
UCSD and Oxford and McGill and Hamburg and a few other libraries have a copy, see [here](https://search.worldcat.org/title/Proceedings-:-Fourth-Hawaii-International-Conference-on-System-Sciences-:-conference-held-January-12-13-14-1971-University-of-Hawaii-Honolulu-Hawaii/oclc/945951774)
Kaveh
CC BY-SA 4.0
2024-03-05T12:45:18.053Z
By the way, the statement is not literally true as written; it suffers from off-by-one errors. See https://cs.stackexchange.com/questions/133521/for-a-binary-tree-of-n-nodes-there-is-a-subtree-with-n-3-to-2n-3-nodes for the $k=2$ case.
Emil Jeřábek
CC BY-SA 4.0
2024-03-06T16:44:48.400Z
Thank you for all the helpful comments. I will try what you suggested, Kaveh. Also, thanks for pointing out the off-by-one error, Emil Jeřábek. I was not aware of that.
user11718766
<cc.complexity-theory><reference-request><co.combinatorics><lo.logic><tree>
Original formulation of Spira's Lemma
user11718766
# Original formulation of Spira's Lemma

(Asked by: username_0 on 2024-03-04)

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!

**Tags:** cc.complexity-theory, reference-request, co.combinatorics, lo.logic, tree
> **Comments:**
> **username_1**: what are $T_a$ and $T^a$?  
> **username_2**: Apparently, it’s actually Fourth Hawaii International *Conference* on System Sciences, cf. https://books.google.cz/books/about/Proceedings_Fourth_Hawaii_International.html?id=Y0zVjwEACAAJ . But I do not know how to get hold of it short of finding a physical copy in a library.  
> **username_2**: @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.  
> **username_3**: To add to Emil's answer, https://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 (https://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.  
> **username_4**: 1. find some folks who might have a paper copy (e.g. Sam Buss) and ask them to send you a scanned copy, 2. go to one of the larger university libraries which might have a copy (University of Toronto did not), 3. use cross-University library services to ask University of Hawaii Library to scan and send you a copy.  
> **username_4**: UCSD and Oxford and McGill and Hamburg and a few other libraries have a copy, see [here](https://search.worldcat.org/title/Proceedings-:-Fourth-Hawaii-International-Conference-on-System-Sciences-:-conference-held-January-12-13-14-1971-University-of-Hawaii-Honolulu-Hawaii/oclc/945951774)  
> **username_2**: By the way, the statement is not literally true as written; it suffers from off-by-one errors. See https://cs.stackexchange.com/questions/133521/for-a-binary-tree-of-n-nodes-there-is-a-subtree-with-n-3-to-2n-3-nodes for the $k=2$ case.  
> **username_0**: Thank you for all the helpful comments. I will try what you suggested, Kaveh. Also, thanks for pointing out the off-by-one error, Emil Jeřábek. I was not aware of that.  

---

## 0 answers

