text:
# Anisotropic spin-glass-like and quasi-one-dimensional magnetic behaviour in an intermetallic compound, Tb2PdSi3

## Abstract

We report temperature dependent ac susceptibility ($`\chi `$) measurements on a high quality single crystal of Tb2PdSi3, crystallizing in a AlB2-derived hexagonal structure. This compound is found to exhibit features attributable to quasi-low-dimensional magnetism at high temperatures and anisotropic spin-glass-like behavior at low temperatures ($`<`$ 10 K) with an unusually large frequency dependence of peak temperature in ac $`\chi `$(T). This compound thus presents a novel situation in metallic magnetism, considering that the former phenomenon is normally encountered only among insulators, whereas the anisotropic spin-glass-like behavior, to our knowledge, has not been known in stoichiometric intermetallic compounds.

PACS Nos. 75.50.-y; 75.50.Lk, 75.30.Cr, 75.20.En

The field of magnetism continues to be an exciting one due to the discovery of magnetic materials with unusual characteristics leading to the discovery of novel phenomena. In recent years, there is a tremendous increase of activities on the materials with magnetic frustration effects leading to spin-glass freezing on one hand, and with low-dimensional effects on the other hand. As far as spin-glass freezing is concerned, it has been generally assumed that this phenomenon is isotropic in stoichiometric compounds. With respect to low-dimensional magnetism, the focus has always been on insulators in which the magnetic ordering is mediated by superexchange mechanism via the intervening non-magnetic atoms. However, the existence of low-dimensional effects, to our knowledge, has not been demonstrated among intermetallic compounds. The existence of a compound with these properties in a metallic environment would be surprising, as the indirect exchange interaction via the conduction electrons in metals, being of a long-range type, is expected to destroy low-dimensional character in favor of three dimensional interaction. In this article, we bring out that the intermetallic compound, Tb2PdSi3, exhibits certain unusual strongly anisotropic features in the temperature (T) dependent ac susceptibility ($`\chi `$), both above and below long range magnetic ordering temperature (close to 24 K), which appear to have some bearing to the above assumptions.

This compound crystalizes in a AlB2-derived hexagonal structure. It is worthwhile stating that the Pd-based ternary compounds R2PdSi3 (R= Rare-earth) have been found to exhibit many interesting and unusual magnetic and transport properties. The properties of the Tb compound are particularly notable. While the reader may see references 6 (on polycrystal) and 12 (on single crystal) for many other interesting properties of this compound, we recall here only those which are relevant to the present article. All the results conclusively establish that long range magnetic ordering sets in below about 24 K. However, the nature of the magnetism appears to be very complex with a strong evidence for the existence of ferromagnetic correlations along basal plane and antiferromagnetic interplane interaction (along c-direction); the moment orientation appears to be on the basal plane. In addition, the dc $`\chi `$ data reveal one more transition below about 10 K in the polycrystal, whereas the data for the single crystal reveal more transitions at lower temperatures depending on the orientation and the (magnetic field and thermal cycling) history of the sample. Another puzzling observation in the dc $`\chi `$(T) plot is that there is a peak at about 55 K for H// (where H is the magnetic field). This peak, extending over a wide temperature range, is very broad, reminiscent of that predicted for one-dimensional magnetism.

The single crystalline sample employed in the present investigation is the same as that in Ref. 12. The ac $`\chi `$ measurements were performed in the T interval 2 - 150 K at various frequencies ($`\nu `$= 1.2, 12, 120 and 1220 Hz) for two crystallographic orientations \[10$`\overline{1}`$0\] and  with respect to the direction of the ac field (2 Oe) on the same piece employing a commercial (Quantum Design) superconducting quantum interference device.

The results of ac $`\chi `$ measurements are shown in Figs. 1 and 2 for the two orientations. It is distinctly clear from the figure 1 that there is a peak at 23.6 K in the real part ($`\chi `$$``$) of ac $`\chi `$ and the peak temperature is independent of $`\nu `$. This establishes that the compound undergoes long range magnetic ordering, but not spin-glass, at 23.6 K. The corresponding feature (appearing as a kink at the same temperature) is extremely weak for H//. There is also a peak in the imaginary part ($`\chi `$$``$) for \[10$`\overline{1}`$0\] at the same temperature, but considering that the peak position is $`\nu `$-independent, one must conclude that the anomalies at 23.6 K do not originate from spin-glass freezing.

The first observation of emphasis is that, as the T is lowered, one observes another peak around 10 K for \[10$`\overline{1}`$0\] for the lowest $`\nu `$ both in $`\chi `$$``$ and $`\chi `$$``$ and the peaks move towards a higher temperature, say, from 10 to 14 K as the $`\nu `$ is varied from 1.2 to 1200 Hz (unlike the 23.6 K transition) (Fig. 1). At this juncture, it may be stated that the neutron diffraction data on polycrystalline material reveal the presence of a spin-glass-like component along with the long-range ordering, which actually prompts us to attribute this frequency dependence to spin-glass-like freezing. But, in Ref. 10, both the orderings are proposed to set in at the same temperature (close to 24 K), whereas in the present study, we observe only long range ordering at 23.6 K with the spin-glass-like features appearing only at 10 K. We believe that this discrepancy arises from the differences in the degree of Pd-Si disorder among these two forms of the material (more in the polycrystalline form) - a finding interesting in its own right. Though this frequence dependence is characteristic of spin-glasses, it is hard to conclude for such anisotropic, concentrated magnetic systems whether the transition is of a spin-glass-type. For this reason, we call this behaviour ”spin-glass-like”. If these properties are truly due to spin-glass behavior, this anomaly in such a stoichiometric compound might arise due to the triangular arrangement of Tb ions (topological frustration) and/or a small degree Pd-Si disorder (see below for a discussion on crystallographic features). In any case, if this feature in this compound is isotropic, one should make similar observations in the data for H//. In sharp contrast to this expectation, we do not see (Fig. 2) any peak in the T range 7 - 12 K for this direction. Thus, the anisotropic nature of the 10K-feature makes this compound an interesting one. However, the $`\chi `$$``$(T) curve for the latter direction shows a drop at a lower temperature, say around 5 K, for $`\nu `$= 1 Hz. In other words, the former direction shows a spin-glass-like feature at about 10 K, whereas the latter orientation shows similar frequency-dependent $`\chi `$$``$ features around 5 K (see the inset of Fig. 1). These findings (low-T transitions at distinctly different temperatures for these two directions) are rather consistent with the features in the zero-field-cooled dc $`\chi `$ data of Ref. 12 (compare Fig 2a and 2b of Ref. 12). The above 5K-feature in any case can not be attributed to ”canonical spin-glass” behavior, as the sign of the magnetoresistance in the vicinity of 5 K (see Fig. 2b of Ref. 12) for H// is opposite (positive!) to that expected for spin-glasses, and that $`\chi `$$``$$``$(T) does not apparently exhibit a sharp feature, however weak it may be, around 4 K. Needless to emphasize that the magnitude of the shift ($`>`$ 2 K) of the peak temperatures with $`\nu `$ for these transitions is interestingly very large compared to that known (about 1$`\%`$) for canonical spin glasses. It is not out of place to mention that we have also measured the isothermal magnetization (M) and we find that M varies esssentially $`\mathrm{𝑙𝑖𝑛𝑒𝑎𝑟𝑙𝑦}`$ for H// without any hysteresis at low fields (below 20 kOe), say at 5 K, as reported in Ref. 12, whereas for H//\[10$`\overline{1}`$0\], M-H plot exhibits a hysteresis loop. Therefore, if the hysteresis in M for the latter orientation arises from spin-glass-like anomaly, then clearly this behavior is anisotropic.

In order to bring out the second major point of emphasis, we turn to the data above 23 K. It is obvious that the $`\chi `$$``$ (T) exhibits a broad peak around 55 K for  as in the case of dc $`\chi `$ (T) plot (see the inset of Fig. 2, with the data taken from Ref. 12). This feature is so broad that it can not result from spin-glass freezing of some fraction of Tb ions. The present article places this on a firm footing by reporting ac $`\chi `$ as a function of $`\nu `$, i.e., the plots for all the frequencies overlap above 25 K.

A careful look at the crystallographic features in light of above finding is quite intriguing. As already remarked, this compound forms in a AlB2-derived hexagonal crystal structure. The ternary derivative of this structure presents an interesting situation (Fig. 3) crystallographically in the event that there is an ordered occupation of B-site by Pd and Si atoms in the basal plane: that is, there are two different chemical environments for R ions (called 2(b) and 6(h) sites), doubling the a-parameter. As a signature of this, one normally observes superstructure lines in the x-ray diffraction pattern (e.g., (101) and (110) appearing at 2$`\theta `$= 16.6 and 21.7 $`\AA `$ respectively with Cu Kα radiation). However, such superstructure lines are usually weak (the intensity of which apparently depends upon the degree of Pd-Si disorder). Hence these can easily escape detection. Thus, the wave-length of the neutron employed in a previous study on the polycrystalline form is too large (2.44 $`\AA `$) that these lines could not be detectable, whereas, in the x-ray diffraction pattern recorded with a much smaller wave-length radiation (Cu Kα) on the same polycrystalline sample, we could observe these lines in agreement with a previous article reporting doubling of a-parameter. While finalising this article, we came to know that careful neutron diffraction investigations on the single crystals indeed reveal the doubling of a-parameter. The R and Pd-Si layers are stacked alternately along c-direction and the arrangement of R ions in the basal plane is triangular. The R ions at the 6(h) site are sandwitched by eight Si atoms and four Pd atoms (with four Si and two Pd placed on the vortices of the hexagon on each side) along the hexagonal tube, whereas the ones at the 2(b) site are sandwiched by hexagons of Si in the immediate vicinity. Thus there are chains of R ions at the centre of the hexagonal tube made up of Pd and Si atoms and the R-R distances are of the order of 4 $`\AA `$. It has been established that the R chain at the 2(b) site can undergo magnetic ordering due to finite interaction among 2(b)-2(b) chains (which are at a distance of about 8 $`\AA `$ from each other) leaving the intervening R ions at the 6(h) site paramagnetic. We therefore attribute the broad 55K-peak in $`\chi `$ to the antiferromagnetic correlations within the chain of Tb ions present at the 2(b) site, and the observed broad peak is similar to that predicted theoretically by Bonner and Fischer several years ago. In order to compare the experimental $`\chi `$ behavior with a model on low dimensional systems, for instance as in Ref. 21), we have used the dc $`\chi `$ data (Ref. 12) (above 25 K) instead of ac $`\chi `$, as the absolute values are more reliable in the former case. We obtained a fairly good fit (see continuous the line in the inset of Fig. 2 as per the equation 2 in Ref. 21) for an exchange interaction strength of about 35 K. The broad peak is however not observable for H//\[10$`\overline{1}`$0\] (see Fig. 1). It is to be remarked that the strength of this peak for H// is very low in the dc $`\chi `$ as well. Such a weak feature is masked for H//\[10$`\overline{1}`$0\] as the $`\chi `$ values for the paramagnetic Tb ions at the 6(h) site for this orientation are large increasing at a faster rate (than the decrease of $`\chi `$ below 45 K in the other direction) with decreasing T. It is worth noting that the paramagnetic Curie temperature is widely different (-30 and 23 K for  and \[10$`\overline{1}`$0\] directions), unlike the situation for other analogous heavy rare-earth compounds. Such a strong anisotropy even in the paramagnetic state is also a characteristic of quasi-one-dimensional magnetic systems.

To conclude, Tb2PdSi3 apparently exhibits quasi-one-dimensional features in the magnetic susceptibility data (around 55 K), thereby characterizing this compound, to our knowledge, to be the first one among intermetallics to show this phenomenon. Naturally, this compound will thus serve as an ideal model system to evolve theories to understand low-dimensional magnetism dominated by indirect exchange interaction via conduction electrons (unlike the situation till todate in insulators in which case superexchange interaction mediates magnetic coupling) and associated interchain coupling effects. Another unusual observation is that, the 23.6K-long-range magnetic ordering is followed by ”anisotropic” spin-glass-like anomalies at lower temperatures; in addition, there is a large frequency dependence of the peak temperature in ac $`\chi `$(T) plot, uncharacteristic of canonical metallic spin-glasses. These results clearly reveal that this compound is an exotic magnetic material.


format: text

text:
# 𝑃≠𝑁𝑃, Propositional Proof Complexity, and Resolution Lower Bounds for the Weak Pigeonhole Principle

## 1. Propositional logic

The basic syntactic units (atoms) of propositional logic are Boolean variables $`x_1,\mathrm{},x_n\{0,1\}`$, where the value 0 represents False and the value 1 represents True. The propositional variables are combined with standard Boolean gates (also called connectives), such as, AND (conjunction), OR (disjunction), and NOT (negation), to form Boolean formulas. Recall that in propositional logic there are no quantifiers.

A literal is either an atom (i.e., a variable $`x_i`$) or the negation of an atom (i.e., $`\neg x_i`$). A clause is a disjunction of literals. A term is a conjunction of literals. A formula $`f`$ is in conjunctive-normal-form (CNF) if it is a conjunction of clauses. A formula $`f`$ is in disjunctive-normal-form (DNF) if it is a disjunction of terms. Since there are standard ways to transform a formula to CNF or DNF (by adding new variables), many times we limit the discussion to CNF formulas or DNF formulas.

A Boolean formula $`f(x_1,\mathrm{},x_n)`$ is a tautology if $`f(x_1,\mathrm{},x_n)=1`$ for every $`x_1,\mathrm{},x_n`$. A Boolean formula $`f(x_1,\mathrm{},x_n)`$ is unsatisfiable if $`f(x_1,\mathrm{},x_n)=0`$ for every $`x_1,\mathrm{},x_n`$. Obviously, $`f`$ is a tautology if and only if $`\neg f`$ is unsatisfiable.

Given a formula $`f(x_1,\mathrm{},x_n)`$, one can decide whether or not $`f`$ is a tautology by checking all the possibilities for assignments to $`x_1,\mathrm{},x_n`$. However, the time needed for this procedure is exponential in the number of variables, and hence may be exponential in the length of the formula $`f`$.

## 2. $`𝑷\mathbf{}𝑵𝑷`$

$`PNP`$ is the central open problem in complexity theory and one of the most important open problems in mathematics today. The problem has thousands of equivalent formulations. One of these formulations is the following:

> Is there a polynomial time algorithm $`A`$ that gets as input a Boolean formula $`f`$ and outputs 1 if and only if $`f`$ is a tautology ?

$`PNP`$ states that there is no such algorithm.

A related open problem in complexity theory is the problem of $`NPCoNP`$. The problem can be stated as follows:

> Is there a polynomial time algorithm $`A`$ that gets as input a Boolean formula $`f`$ and a string $`z`$, and such that: $`f`$ is a tautology if and only if there exists $`z`$ s.t.:
>
> 1. The length of $`z`$ is at most polynomial in the length of $`f`$.
> 2. $`A(f,z)=1`$.

$`NPCoNP`$ states that there is no such algorithm. Obviously, $`NPCoNP`$ implies $`PNP`$.

It is widely believed that $`PNP`$ (and $`NPCoNP`$). At this point, however, we are still far from giving a solution for these problems. It is not clear why these problems are so hard to solve.

## 3. Propositional proof theory

Propositional proof theory is the study of the length of proofs for different tautologies in different propositional proof systems.

The notion of propositional proof system was introduced by Cook and Reckhow in 1973, as a direction for proving $`NPcoNP`$ (and hence also $`PNP`$. A propositional proof system is a polynomial time algorithm $`A(f,z)`$ such that a Boolean formula $`f`$ is a tautology if and only if there exists $`z`$ such that $`A(f,z)=1`$ (note that we do not require here that the length of $`z`$ is at most polynomial in the length of $`f`$). We think of the string $`z`$ as a proof for $`f`$ in the proof system $`A`$. We say that a tautology $`f`$ is hard for a proof system $`A`$ if any proof $`z`$ for $`f`$ in the proof system $`A`$ is of length super-polynomial in the length of $`f`$.

Many times we prefer to talk about unsatisfiable formulas, rather than tautologies, and about refutation systems, rather than proof systems. A propositional refutation system is a polynomial time algorithm $`A(f,z)`$ such that a Boolean formula $`f`$ is unsatisfiable if and only if there exists $`z`$ such that $`A(f,z)=1`$. We think of the string $`z`$ as a refutation for $`f`$ in the refutation system $`A`$. We think of a refutation $`z`$ for $`f`$ also as a proof for $`\neg f`$ (and vice versa).

It is easy to see that $`NPcoNP`$ if and only if for every propositional proof system $`A`$ there exists a hard tautology, that is, a tautology $`f`$ with no short proofs. It was hence suggested by Cook and Reckhow to study the length of proofs for different tautologies in stronger and stronger propositional proof systems. It turns out that in many cases these problems are very interesting in their own right and are related to many other interesting problems in complexity theory and in logic, in particular when the tautology $`f`$ represents a fundamental mathematical principle.

For a recent survey on the main research directions in propositional proof theory, see .

## 4. Resolution

Resolution is one of the simplest and most widely studied propositional proof systems. Besides its mathematical simplicity and elegance, Resolution is a very interesting proof system also because it generalizes the Davis-Putnam procedure and several other well known proof-search procedures. Moreover, Resolution is the base for most automat theorem provers existing today.

The Resolution rule says that if $`C`$ and $`D`$ are two clauses and $`x_i`$ is a variable then any assignment (to the variables $`x_1,\mathrm{},x_n`$) that satisfies both of the clauses, $`Cx_i`$ and $`D\neg x_i`$, also satisfies the clause $`CD`$. The clause $`CD`$ is called the resolvent of the clauses $`Cx_i`$ and $`D\neg x_i`$ on the variable $`x_i`$.

Resolution is usually presented as a propositional refutation system for CNF formulas. Since there are standard ways to transform a formula to CNF (by adding new variables), this presentation is general enough. A Resolution refutation for a CNF formula $`f`$ is a sequence of clauses $`C_1,C_2,\mathrm{},C_s`$, such that:

1. Each clause $`C_j`$ is either a clause of $`f`$ or a resolvent of two previous clauses in the sequence.
2. The last clause, $`C_s`$, is the empty clause.

We think of the empty clause as a clause that has no satisfying assignments, and hence a contradiction was obtained.

We think of a Resolution refutation for $`f`$ also as a proof for $`\neg f`$. Without loss of generality, we assume that no clause in a Resolution proof contains both $`x_i`$ and $`\neg x_i`$ (such a clause is always satisfied and hence it can be removed from the proof). The length, or size, of a Resolution proof is the number of clauses in it.

We can represent a Resolution proof as an acyclic directed graph on vertices $`C_1,\mathrm{},C_s`$, where each clause of $`f`$ has out-degree 0, and any other clause has two edges pointing to the two clauses that were used to produce it.

It is well known that Resolution is a refutation system. That is, a CNF formula $`f`$ is unsatisfiable if and only if there exists a Resolution refutation for $`f`$. A well-known and widely studied restricted version of Resolution (that is still a refutation system) is called Regular Resolution. In a Regular Resolution refutation, along any path in the directed acyclic graph, each variable is resolved upon at most once.

## 5. Resolution as a search problem

As mentioned above, we represent a Resolution proof as an acyclic directed graph $`G`$ on the vertices $`C_1,\mathrm{},C_s`$. In this graph, each clause $`C_j`$ which is an original clause of $`f`$ has out-degree 0, and any other clause has two edges pointing to the two clauses that were used to produce it. We call the vertices of out-degree 0 (i.e., the clauses that are original clauses of $`f`$) the leaves of the graph. Without loss of generality, we can assume that the only clause with in-degree 0 is the last clause $`C_s`$ (as we can just remove any other clause with in-degree 0). We call the vertex $`C_s`$ the root of the graph.

We label each vertex $`C_j`$ in the graph by the variable $`x_i`$ that was used to derive it (i.e., the variable $`x_i`$ that was resolved upon), unless the clause $`C_j`$ is an original clause of $`f`$ (and then $`C_j`$ is not labelled). If a clause $`C_j`$ is labelled by a variable $`x_i`$ we label the two edges going out from $`C_j`$ by 0 and 1, where the edge pointing to the clause that contains $`x_i`$ is labelled by 0, and the edge pointing to the clause that contains $`\neg x_i`$ is labelled by 1. That is, if the clause $`CD`$ was derived from the two clauses $`Cx_i`$ and $`D\neg x_i`$ then the vertex $`CD`$ is labelled by $`x_i`$, the edge from the vertex $`CD`$ to the vertex $`Cx_i`$ is labelled by 0 and the edge from the vertex $`CD`$ to the vertex $`D\neg x_i`$ is labelled by 1. For a non-leaf node $`u`$ of the graph $`G`$, define,

> $`\mathrm{𝐋𝐚𝐛𝐞𝐥}(𝐮)=`$ the variable labelling $`u`$.

We think of $`Label(u)`$ as a variable queried at the node $`u`$.

Let $`p`$ be a path on $`G`$, starting from the root. Note that along a path $`p`$, a variable $`x_i`$ may appear (as a label of a node $`u`$) more than once. We say that the path $`p`$ evaluates $`x_i`$ to 0 if $`x_i=Label(u)`$ for some node $`u`$ on the path $`p`$, and after the last appearance of $`x_i`$ as $`Label(u)`$ (of a node $`u`$ on the path) the path $`p`$ continues on the edge labelled by 0 (i.e., if $`u`$ is the last node on $`p`$ such that $`x_i=Label(u)`$ then $`p`$ contains the edge labelled by 0 that goes out from $`u`$). In the same way, we say that the path $`p`$ evaluates $`x_i`$ to 1 if $`x_i=Label(u)`$ for some node $`u`$ on the path $`p`$, and after the last appearance of $`x_i`$ as $`Label(u)`$ (of a node $`u`$ on the path) the path $`p`$ continues on the edge labelled by 1 (i.e., if $`u`$ is the last node on $`p`$ such that $`x_i=Label(u)`$ then $`p`$ contains the edge labelled by 1 that goes out from $`u`$).

For any node $`u`$ of the graph $`G`$, we define $`Zeros(u)`$ to be the set of variables that the node $`u`$ “remembers” to be 0, and $`Ones(u)`$ to be the set of variables that the node $`u`$ “remembers” to be 1, that is,

> $`\mathrm{𝐙𝐞𝐫𝐨𝐬}(𝐮)=`$ the set of variables that are evaluated to 0 by every path $`p`$ from the root to $`u`$.

> $`\mathrm{𝐎𝐧𝐞𝐬}(𝐮)=`$ the set of variables that are evaluated to 1 by every path $`p`$ from the root to $`u`$.

Note that for any $`u`$, the two sets $`Zeros(u)`$ and $`Ones(u)`$ are disjoint.

The following proposition gives the connection between the sets $`Zeros(u)`$, $`Ones(u)`$ and the literals appearing in the clause $`u`$. The proposition is particularly interesting when $`u`$ is a leaf of the graph.

###### Proposition 1

Let $`f`$ be an unsatisfiable CNF formula and let $`G`$ be (the graph representation of) a Resolution refutation for $`f`$. Then, for any node $`u`$ of $`G`$ and for any $`x_i`$, if the literal $`x_i`$ appears in the clause $`u`$ then $`x_iZeros(u)`$, and if the literal $`\neg x_i`$ appears in the clause $`u`$ then $`x_iOnes(u)`$.

## 6. The weak pigeonhole principle

The Pigeonhole Principle (PHP) is probably the most widely studied tautology in propositional proof theory. The tautology $`PHP_n`$ is a DNF encoding of the following statement: There is no one to one mapping from $`n+1`$ pigeons to $`n`$ holes. The Weak Pigeonhole Principle (WPHP) is a version of the pigeonhole principle that allows a larger number of pigeons. The tautology $`WPHP_n^m`$ (for $`mn+1`$) is a DNF encoding of the following statement: There is no one to one mapping from $`m`$ pigeons to $`n`$ holes. For $`m>n+1`$, the weak pigeonhole principle is a weaker statement than the pigeonhole principle. Hence, it may have much shorter proofs in certain proof systems.

The weak pigeonhole principle is one of the most fundamental combinatorial principles. In particular, it is used in most probabilistic counting arguments and hence in many combinatorial proofs. Moreover, as observed by Razborov, there are certain connections between the weak pigeonhole principle and the problem of $`PNP`$ . Indeed, the weak pigeonhole principle (with a relatively large number of pigeons) can be interpreted as a certain encoding of the following statement: There are no small DNF formulas for $`SAT`$ (where $`SAT`$ is the satisfiability problem). Hence, in most proof systems, a short proof for certain formulations of the statement “There are no small formulas for $`SAT`$” can be translated into a short proof for the weak pigeonhole principle. That is, a lower bound for the length of proofs for the weak pigeonhole principle usually implies a lower bound for the length of proofs for certain formulations of the statement $`PNP`$. While this doesn’t say much about the problem of $`PNP`$, it does demonstrate the applicability and relevance of the weak pigeonhole principle for other interesting problems.

Formally, the formula $`WPHP_n^m`$ is expressed in the following way. The underlying Boolean variables, $`x_{i,j}`$, for $`1im`$ and $`1jn`$, represent whether or not pigeon $`i`$ is mapped to hole $`j`$. The negation of the pigeonhole principle, $`\neg WPHP_n^m`$, is expressed as the conjunction of $`m`$ pigeon clauses and $`\left(\genfrac{}{}{0pt}{}{m}{2}\right)n`$ hole clauses. For every $`1im`$, we have a pigeon clause,

$$(x_{i,1}\mathrm{}x_{i,n}),$$

stating that pigeon $`i`$ maps to some hole. For every $`1i_1<i_2m`$ and every $`1jn`$, we have a hole clause,

$$(\neg x_{i_1,j}\neg x_{i_2,j}),$$

stating that pigeons $`i_1`$ and $`i_2`$ do not both map to hole $`j`$. We refer to the pigeon clauses and the hole clauses also as pigeon axioms and hole axioms. Note that $`\neg WPHP_n^m`$ is a CNF formula.

Let $`G`$ be (the graph representation of) a Resolution refutation for $`\neg WPHP_n^m`$. Then, by Proposition 1, for any leaf $`u`$ of the graph $`G`$, one of the following is satisfied:

1. $`u`$ is a pigeon axiom, and then for some $`1im`$, the variables $`x_{i,1},\mathrm{},x_{i,n}`$ are all contained in $`Zeros(u)`$.
2. $`u`$ is a hole axiom, and then for some $`1jn`$, there exist two different variables $`x_{i_1,j},x_{i_2,j}`$ in $`Ones(u)`$.

## 7. Resolution lower bounds for the weak pigeonhole principle

There are trivial Resolution proofs (and Regular Resolution proofs) of length $`2^npoly(n)`$ for the pigeonhole principle and for the weak pigeonhole principle. In a seminal paper, Haken proved that for the pigeonhole principle, the trivial proof is (almost) the best possible . More specifically, Haken proved that any Resolution proof for the tautology $`PHP_n`$ is of length $`2^{\mathrm{\Omega }(n)}`$. Haken’s argument was further developed in several other papers (e.g., ). In particular, it was shown that a similar argument gives lower bounds also for the weak pigeonhole principle, but only for small values of $`m`$. More specifically, super-polynomial lower bounds were proved for any Resolution proof for the tautology $`WPHP_n^m`$, for $`m<cn^2/\mathrm{log}n`$ (for some constant $`c`$) .

For the weak pigeonhole principle with large values of $`m`$, there do exist Resolution proofs (and Regular Resolution proofs) which are much shorter than the trivial ones. In particular, it was proved by Buss and Pitassi that for $`m>c^{\sqrt{n\mathrm{log}n}}`$ (for some constant $`c`$), there are Resolution (and Regular Resolution) proofs of length $`poly(m)`$ for the tautology $`WPHP_n^m`$ . Can this upper bound be further improved ? Can one prove a matching lower bound ? A partial progress was made by Razborov, Wigderson and Yao, who proved exponential lower bounds for Regular Resolution proofs, but only when the Regular Resolution proof is of a certain restricted form .

The weak pigeonhole principle with large number of pigeons has attracted a lot of attention in recent years. However, the standard techniques for proving lower bounds for Resolution failed to give lower bounds for the weak pigeonhole principle. In particular, for $`mn^2`$, no non-trivial lower bound was known until very recently.

In the last two years, these problems were completely solved. An exponential lower bound for any Regular Resolution proof was proved in , and an exponential lower bound for any Resolution proof was finally proved in . More precisely, it was proved in  that for any $`m`$, any Resolution proof for the weak pigeonhole principle $`WPHP_n^m`$ is of length $`\mathrm{\Omega }(2^{n^ϵ})`$, where $`ϵ>0`$ is some global constant ($`ϵ1/8`$).

The lower bound was further improved in several results by Razborov. The first result  presents a proof for an improved lower bound of $`\mathrm{\Omega }(2^{n^ϵ})`$, for $`ϵ=1/3`$. The second result  extends the lower bound to an important variant of the pigeonhole principle, the so called weak functional pigeonhole principle, where we require in addition that each pigeon goes to exactly one hole. The third result  extends the lower bound to another important variant of the pigeonhole principle, the so called weak functional onto pigeonhole principle, where we require in addition that every hole is occupied.

For a recent survey on the propositional proof complexity of the pigeonhole principle, see .

## 8. Lower bounds for $`𝑷\mathbf{}𝑵𝑷`$

Propositional versions of the statement $`PNP`$ were introduced by Razborov in 1995  (see also ). Razborov suggested to try to prove super-polynomial lower bounds for the length of proofs for these statements in stronger and stronger propositional proof systems. This was suggested as a step for proving the hardness of proving $`PNP`$. The above mentioned results for the weak pigeonhole principle establish such super-polynomial lower bounds for Resolution.

Let $`g:\{0,1\}^d\{0,1\}`$ be a Boolean function. For example, we can take $`g=SAT`$, where $`SAT:\{0,1\}^d\{0,1\}`$ is the satisfiability function (or we can take any other $`NP`$-hard function). We assume that we are given the truth table of $`g`$. Let $`t2^d`$ be some integer. We think of $`t`$ as a large polynomial in $`d`$, say $`t=d^{1000}`$.

Razborov suggested to study propositional formulations of the following statement (in the variables $`\stackrel{}{Z}`$):

> $`\stackrel{}{Z}`$ is (an encoding of) a Boolean circuit of size $`t`$ $``$
> $`\stackrel{}{Z}`$ does not compute the function $`g`$.

Note that since the truth table of $`g`$ is of length $`2^d`$, a propositional formulation of this statement will be of length at least $`2^d`$, and it is not hard to see that there are ways to write this statement as a DNF formula of length $`2^{O(d)}`$ (and hence, its negation is a CNF formula of that length). The standard way to do that is by including in $`\stackrel{}{Z}`$ both, the (topological) description of the Boolean circuit, as well as the value that each gate in the circuit outputs on each input for the circuit.

In , Razborov presented a lower bound for the degree of Polynomial Calculus proofs for the weak pigeonhole principle, and used this result to prove a lower bound for the degree of Polynomial Calculus proofs for a certain version of the above statement. Following this line of research, it was proved in  (in a similar way) that if $`t`$ is a large enough polynomial in $`d`$ (say $`t=d^{1000}`$) then any Resolution proof for certain versions of the above statement is of length super-polynomial in $`2^d`$, that is, super-polynomial in the length of the statement.

In particular, this can be interpreted as a super-polynomial lower bound for Resolution proofs for certain formulations of the statement $`PNP`$ (or, more precisely, of the statement $`NP\overline{)}P/poly`$).

It turns out that the exact way to give the (topological) description of the circuit is also important in some cases. This was done slightly differently in  and in . In , $`\stackrel{}{Z}`$ was used to encode a Boolean circuit of unbounded fan-in, whereas  considered Boolean circuits of fan-in 2. It turns out that for the stronger case of unbounded fan-in, the lower bound for the weak pigeonhole principle is enough , whereas for the weaker case of fan-in 2 one needs the lower bound for the weak functional onto pigeonhole principle  (in fact, this was one of the main motivations to consider the onto functional case). Otherwise, the proof seems to be quite robust in the way the Boolean circuit is encoded.

Acknowledgement. I would like to thank Toni Pitassi for very enjoying collaboration that lead to the results in .