concurring in part, dissenting in part:
I concur in the judgment to the extent the majority opinion affirms the district court’s denial of Ceja’s habeas challenge to his conviction. I respectfully dissent from the affir-mance of Ceja’s sentence.
I would hold that the Arizona courts’ failure to find the F(6) aggravating factor beyond a reasonable doubt was constitutional error that had a substantial and injurious effect on the sentence. I disagree with the majority that we may presume that the Arizona courts found the F(6) factor beyond a reasonable doubt. Nowhere in the trial court or state supreme court’s opinions is there any reference to having found the factor beyond a reasonable doubt. Arizona’s death penalty statute does not by its terms provide that aggravating factors must be proven beyond a reasonable doubt. See *1256State v. Jordan, 126 Ariz. 283, 614 P.2d 825, 828, cert. denied, 449 U.S. 986, 101 S.Ct. 408, 66 L.Ed.2d 251 (1980) (“The statute does not indicate the degree of certainty with which these circumstances must be established.”). It was not until one month after Ceja’s sentence was affirmed by the Arizona Supreme Court that the Arizona Supreme Court first held that Arizona’s death penalty statute required that aggravating factors be proved beyond a reasonable doubt. Jordan, 614 P.2d at 828.
We presume that state courts follow the law. Jeffers v. Lewis, 38 F.3d 411, 415 (9th Cir.1994), cert. denied, — U.S. -, 115 S.Ct. 1709, 131 L.Ed.2d 570 (1995). Thus, we presumed that the Arizona Supreme Court applied the reasonable doubt standard to an appeal decided shortly after Jordan was decided. Clark v. Ricketts, 958 F.2d 851, 860 (9th Cir.), cert. denied, 506 U.S. 838, 113 S.Ct. 117, 121 L.Ed.2d 73 (1992). However, we have never presumed that state courts follow law that has not yet been decided. Cf. Southern Pac. Co. v. Jensen, 244 U.S. 205, 222, 37 S.Ct. 524, 531, 61 L.Ed. 1086 (1917) (Holmes, J., dissenting) (law is not a “brooding omnipresence in the sky but the articulate voice of some sovereign or quasi-sovereign that can be identified”). That the Arizona Supreme Court subsequently stated that it had “always assumed ... that the state must prove the existence of aggravating circumstances beyond a reasonable doubt,” Jordan, 614 P.2d at 828, is not evidence that it found the F(6) factor in Ceja’s case. This is essentially a post-decision statement by the members of the Arizona Supreme Court as to their mental processes at the time they affirmed Ceja’s sentence, which may not be used as evidence in a subsequent challenge to the decision. See Fayerweather v. Ritch, 195 U.S. 276, 306-07, 25 S.Ct. 58, 67-68, 49 L.Ed. 193 (1904) (testimony of the mental processes of a judge not to be considered); Perkins v. LeCureux, 58 F.3d 214, 220 (6th Cir.) (“[Pjost-decision statements by a judge ... about his mental processes in reaching decision may not be used as evidence in a subsequent challenge to the decision.”) (quoting Proffitt v. Wainwright, 685 F.2d 1227, 1255 (11th Cir.1982) (relying on Fayer-weather)), cert. denied, — U.S. -, 116 S.Ct. 526, 133 L.Ed.2d 432 (1995). A state cannot excuse its failure to find the existence of an aggravating factor beyond a reasonable doubt by stating in a later opinion that it had always assumed that reasonable doubt was required, although up to that time it had never so held or even implied in any of its opinions.
This failure by the Arizona courts to find the F(6) factor beyond a reasonable doubt violated Ceja’s constitutional rights. Although sentencing factors are not elements of the crime and generally do not require a heightened standard of proof, United States v. Restrepo, 946 F.2d 654 (9th Cir.1991) (en bane), cert. denied, 503 U.S. 961, 112 S.Ct. 1564, 118 L.Ed.2d 211 (1992), the Supreme Court has recognized “that there may be an exception to the general rule that the preponderance standard satisfies due process when a sentencing factor has an extremely disproportionate effect on the sentence relative to the offense of conviction.” Id. at 659 (citing McMillan v. Pennsylvania, 477 U.S. 79, 106 S.Ct. 2411, 91 L.Ed.2d 67 (1986)). The difference between life and death decided on the basis of whether an aggravating factor exists warrants such an exception, particularly in light of the Eighth Amendment’s “guarantee against the arbitrary or capricious imposition of the death penalty.” Lewis v. Jeffers, 497 U.S. 764, 782, 110 S.Ct. 3092, 3103, 111 L.Ed.2d 606 (1990).
The Supreme Court’s opinion in Lewis v. Jeffers further supports the conclusion that aggravating factors used to determine whether a defendant will be executed must be proven beyond a reasonable doubt. In Lewis, the Supreme Court held that the appropriate standard of federal habeas review of a state court’s application of an aggravating circumstance is the “rational factfinder” standard established in Jackson v. Virginia, 443 U.S. 307, 99 S.Ct. 2781, 61 L.Ed.2d 560 (1979), i.e., “whether, after viewing the evidence in the light most favorable to the prosecution, any rational trier of fact could have found the essential elements of the crime beyond a reasonable doubt.” 497 U.S. at 781, 110 S.Ct. at 3102-03 (quoting Jackson, 443 U.S. at 319, 99 S.Ct. at 2789 (citation *1257omitted)). The Court explained, “Although aggravating circumstances are not ‘elements’ of any offense, the standard of federal review for determining whether a state court has violated the Fourteenth Amendment’s guarantee against wholly arbitrary deprivations of liberty is equally applicable in safeguarding the Eighth Amendment’s bedrock guarantee against the arbitrary or capricious imposition of the death penalty.” Id. at 782, 110 S.Ct. at 3103. Because federal courts must review for whether any rational trier of fact could have found the essential elements of the aggravating factor beyond a reasonable doubt, the trier of fact is required to find the elements beyond a reasonable doubt. If, by contrast, the sentencer needed to find the elements underlying the aggravating factor only by a preponderance of the evidence, the federal court’s review would be whether any rational trier of fact could have found the elements by a preponderance of the evidence. Cf. Creech v. Arave, 947 F.2d 873, 882 (9th Cir.1991), rev’d in part on other grounds, 507 U.S. 463, 113 S.Ct. 1534, 123 L.Ed.2d 188 (1993) (overturning a death sentence in a habeas proceeding because the trial court failed to find specific intent “beyond a reasonable doubt,” without discussing whether the reasonable doubt requirement was based on federal or state law).
I would thus hold that Ceja has an Eighth Amendment right not to be put to death on the basis of aggravating factors not found beyond a reasonable doubt by the trier of fact. The Arizona courts’ failure to find the F(6) factor beyond a reasonable doubt had a “substantial and injurious effect on the verdict” of death that warrants reversal on ha-beas review. Brecht v. Abrahamson, 507 U.S. 619, 637, 113 S.Ct. 1710, 1721-22, 123 L.Ed.2d 353 (1993); see Sullivan v. Louisiana, 508 U.S. 275, 113 S.Ct. 2078, 124 L.Ed.2d 182 (1993) (constitutionally erroneous reasonable-doubt instruction warrants reversal of conviction on habeas review).
Because the Arizona courts’ failure to find the F(6) factor beyond a reasonable doubt warrants the setting aside of Ceja’s sentence, I would not reach Ceja’s other challenges to his sentence. As the majority rejects these challenges, however, I note my disagreement on three additional claims.
First, I disagree with the majority that a rational factfinder could have found the F(6) factor beyond a reasonable doubt. There was not sufficient admissible evidence to support the finding that Ceja repeatedly kicked Randy Leon in the head. The only evidence the majority cites in support of this finding is detective Ysasi’s statement at the sentencing hearing that he “did not know why [Ceja] kicked [Randy] in the head.” However, Detective Ysasi’s statement came in response to a question that assumed the fact of kicking without adequate foundation, so the statement is not itself evidence that Ceja kicked Randy Leon. Regardless of whether the evidence that Ceja shot Linda Leon four times and Randy Leon six times is sufficient to establish heinousness or depravity, cf. Richmond v. Lewis, 506 U.S. 40, 51, 113 S.Ct. 528, 536-37, 121 L.Ed.2d 411 (1982), the F(6) finding cannot stand. The Arizona Supreme Court’s determination that the killings were heinous and depraved was based upon “the totality of the circumstances of both killings,” State v. Ceja, 126 Ariz. 35, 612 P.2d 491, 495 (1980). Thus, if the evidence was insufficient to support the kicking finding, the supreme court would have to reexamine the totality of other circumstances, absent any kicking, to determine whether the killings were heinous or depraved.
Second, I disagree with the majority that Arizona had adequately narrowed and applied the F(6) factor at the time of Ceja’s sentencing. Ceja’s death sentence is premised on a single statutory aggravating factor-that “[t]he defendant committed the offense in an especially heinous, cruel or depraved manner.” Ariz.Rev.Stat. § 13-703(F)(6). As the majority acknowledges, this factor is facially vague. Walton v. Arizona, 497 U.S. 639, 652-55, 110 S.Ct. 3047, 3056-58, 111 L.Ed.2d 511 (1990); see also Maynard v. Cartwright, 486 U.S. 356, 363-64, 108 S.Ct. 1853, 1858-59, 100 L.Ed.2d 372 (1988) (holding that Oklahoma’s “especially heinous, atrocious, or cruel” aggravating circumstance is unconstitutionally vague). Whether this facially vague aggravating factor had been constitutionally narrowed so that the sen-*1258teneer’s “discretion [was] suitably directed and limited,” Gregg v. Georgia, 428 U.S. 153, 96 S.Ct. 2909, 49 L.Ed.2d 859 (1976), is a federal issue subject to de novo review. See Walton, 497 U.S. at 652-55, 110 S.Ct. at 3056-58; Maynard, 486 U.S. at 361, 108 S.Ct. at 1857-58.
The Arizona Supreme Court had not sufficiently narrowed the F(6) factor prior to Ceja’s sentencing in 1979. At that time, the Arizona Supreme Court had decided just one major case construing the F(6) factor, State v. Knapp, 114 Ariz. 531, 562 P.2d 704 (1977), cert denied, 435 U.S. 908, 98 S.Ct. 1458, 55 L.Ed.2d 500 (1978).1 Knapp states that the words “cruel, heinous, and depraved” provide sufficient guidance to the sentencer, id. at 716 (“[t]he words ... have meanings that are clear to a person of average intelligence and understanding”), a proposition that has since been squarely rejected by the Supreme Court. Walton, 497 U.S. at 654, 110 S.Ct. at 3057-58; Maynard, 486 U.S. at 363-64, 108 S.Ct. at 1858-59. In explaining what the words mean, Knapp quotes Webster’s dictionary definitions of the words:
heinous: hatefully or shockingly evil: grossly bad.
cruel: disposed to inflict pain esp. in a wanton, insensate or vindictive manner: sadistic.
depraved: marked by debasement, corruption, perversion or deterioration.
Id at 716. These equally vague definitions do not constitute.sufficient narrowing. See Shell v. Mississippi, 498 U.S. 1, 111 S.Ct. 313, 112 L.Ed.2d 1 (1990) (per curiam); 498 U.S. at 2-3, 111 S.Ct. at 313-14 (Marshall, J., concurring) (vagueness of “heinous” aggravating factor not cured when defined as “wicked or shockingly evil”).
The Supreme Court’s decision in Richmond v. Lewis provides further support for the conclusion that the Arizona Supreme Court had not adequately narrowed the F(6) factor at the time of Ceja’s sentencing. Richmond was predicated on the assumption that the Arizona Supreme Court had not adequately narrowed the F(6) factor in March 1980, years after Ceja was resen-tenced. See Richmond, 506 U.S. at 47, 113 S.Ct. at 534 (“Respondents do not argue that the factor had been narrowed adequately prior to petitioner’s resentencing. Thus it would have been error for Judge Roylston to give weight to the (F)(6) factor [at petitioner’s resentencing in March 1980].”) (emphasis added). As the State previously conceded that the F(6) factor had not been adequately narrowed as late as 1980 and the Supreme Court consequently held that it was error for the trial judge to give weight to that factor in 1980, I do not see how we can conclude that the trial court’s decision to sentence Ceja to death on the basis of the F(6) factor in 1977 was anything but error.
The Arizona Supreme Court affirmed Ceja’s death sentence in May 1980. Ceja, *1259126 Ariz. 35, 612 P.2d 491. The United States Supreme Court has said that even if the trial judge relied on an invalid factor, the state appellate court can cure this error by performing a new sentencing calculus. Richmond, 506 U.S. at 49, 113 S.Ct. at 535-36. Thus, if the Arizona Supreme Court had performed a new sentencing calculus, the relevant date for purposes of our review would be May 1980. But the Arizona Supreme Court did not do so.2 Although the court found the evidence sufficient to establish the “heinous or depraved” portion of F(6), this is different from concluding that the sentencer would have found that the murder was especially heinous or depraved had its discretion been suitably guided. The court did not reweigh or engage in constitutional harmless error review.
And, lastly, unlike other cases decided at the time, the court did not do a proportionality review to determine independently whether Ceja’s sentence was appropriate. I disagree with the majority that Ceja’s constitutional rights were not violated by the Arizona Supreme Court’s failure to engage in proportionality review. While there is no federal Constitutional right to proportionality review, Pulley v. Harris, 465 U.S. 37, 50-51, 104 S.Ct. 871, 879-80, 79 L.Ed.2d 29 (1984), state law may create liberty interests protected by the Due Process Clause. Wolff v. McDonnell, 418 U.S. 539, 557, 94 S.Ct. 2963, 2975, 41 L.Ed.2d 935 (1974).
Although Arizona does not require proportionality review by statute, the Arizona Supreme Court required such review at the time that it reviewed Ceja’s third death sentence, because the court then believed that it “could not conduct a ‘meaningful appellate review of each death sentence’ without determining whether the sentence of death is disproportionate to the penalty imposed in similar cases.” State v. White, 168 Ariz. 500, 815 P.2d 869, 888 (1991) (quoting State v. Richmond, 114 Ariz. 186, 560 P.2d 41, 51 (1976), cert. denied, 433 U.S. 915, 97 S.Ct. 2988, 53 L.Ed.2d 1101 (1977)), cert. denied, 502 U.S. 1105, 112 S.Ct. 1199, 117 L.Ed.2d 439 (1992). In 1992, a reconstituted court held that proportionality review was no longer required because of perceived defects in the way the reviews were conducted and the court’s belief that other safeguards in the state’s capital punishment scheme were adequate. State v. Salazar, 173 Ariz. 399, 844 P.2d 566, 583 (1992), cert. denied, 509 U.S. 912, 113 S.Ct. 3017, 125 L.Ed.2d 707 (1993); White, 815 P.2d at 886-93.
“State law ... that guarantees a criminal defendant procedural rights at sentencing, may give rise to a state-created liberty interest protected from arbitrary deprivation by the Fourteenth Amendment’s Due Process clause.” Jeffers v. Lewis, 38 F.3d 411, 415 (9th Cir.1994). Integral aspects of a state’s capital sentencing scheme that ensure fairness and uniformity create liberty interests protected by the Due Process Clause.
[Wjhere a state has provided a specific method for the determination of whether the death penalty shall be imposed, “it is not correct to say the defendant’s interest” in having that method adhered to “is merely a matter of state procedural law.” Id. at 346, 100 S.Ct. at 2229.
Fetterly v. Paskett, 997 F.2d 1295, 1300 (9th Cir.1993), amended, 15 F.3d 1472 (9th Cir.1994) (finding a cognizable due process claim based upon the trial judge’s failure to comply with an Idaho statute requiring that each individual aggravating circumstance be weighed against all mitigating factors), cert. *1260denied, — U.S. -, 115 S.Ct. 290, 130 L.Ed.2d 205 (1994).
The Supreme Court has required states to adopt capital punishment procedures that assure reliability in sentencing determinations. Barclay v. Florida, 463 U.S. 939, 958-59, 103 S.Ct. 3418, 3429-30, 77 L.Ed.2d 1134 (1983) (Stevens, J., concurring). As we noted in Fetterly,
[p]art of the requirement of reliability is “that the reasons present in one case will reach a similar result to that reached under similar circumstances in another case.” Because Fetterly may not have been sentenced to death as prescribed by [Idaho law], this goal of similar sentences in similar cases may not have been met. If the sentencing judge did not follow Idaho’s statutory procedures in Fetterly’s case, others similarly sentenced in Idaho have been and will necessarily be treated differently. ...
997 F.2d at 1299 (internal citations omitted). The same can be said here: The Arizona Supreme Court’s failure to conduct a proportionality review in Ceja’s case means that others similarly sentenced in Arizona were treated differently. A state may not “ignore the essentials of its own Gregg required rules regarding the manner in which the core decision of who shall live and who shall die is made.... By definition, the life or death decision necessarily becomes arbitrary if the maimer in which it is made is not authorized by the controlling law.” Fetterly, 15 F.3d at 1483 (Trott, J., concurring in denial of request for en bane review). A state may choose merely to narrow its aggravating circumstances as a way of ensuring reliability in its sentencing. Walton v. Arizona, 497 U.S. 639, 110 S.Ct. 3047, 111 L.Ed.2d 511 (1990). However, once a state uses particular procedures such as proportionality review to ensure reliability and equity among defendants, these procedures must be applied equally to all defendants. The Arizona Supreme Court considered proportionality review to be an integral part of a scheme to ensure that imposition of death sentences was not “excessive or disproportionate” at the time it affirmed Ceja’s sentence. Richmond, 560 P.2d at 51. Thus, Ceja was constitutionally entitled to such a review.3 Cf. Collins v. Francis, 728 F.2d 1322 (11th Cir.) (although proportionality review is not constitutionally mandated, once a state establishes a right to such review defendants have a constitutional right to have it conducted fairly), cert. denied, 469 U.S. 963, 105 S.Ct. 361, 83 L.Ed.2d 297 (1984); Campbell v. Blodgett, 997 F.2d 512, 522 (9th Cir.1992) (Washington law requiring the state supreme court to review each capital sentence imposed to determine whether the sentence of death was imposed through passion or prejudice created for capital defendants a protected liberty interest in having such a review), cert. denied, — U.S. -, 114 S.Ct. 2125, 128 L.Ed.2d 682 (1994); United States v. Woodruff, 50 F.3d 673 (9th Cir.1995) (Nevada law requiring court to review and make particularized findings that it is “just and proper” for defendant to be adjudged habitual offender creates constitutionally protected liberty interest).4
*1261As these errors had a substantial and injurious effect on the sentence, I would grant the petition for writ of habeas corpus to the extent of setting aside Ceja’s death sentence.
. The Arizona Supreme Court had also decided State v. Richmond, 114 Ariz. 186, 560 P.2d 41 (1976), cert. denied, 433 U.S. 915, 97 S.Ct. 2988, 53 L.Ed.2d 1101 (1977), State v. Blazak, 114 Ariz. 199, 560 P.2d 54 (1977), and State v. Watson, 120 Ariz. 441, 586 P.2d 1253 (1978), cert. denied, 440 U.S. 924, 99 S.Ct. 1254, 59 L.Ed.2d 478 (1979), and its previous opinion in Ceja, 115 Ariz. 413, 565 P.2d 1274 (1977), cert. denied, 434 U.S. 975, 98 S.Ct. 533, 54 L.Ed.2d 467 (1977) at the time of Ceja’s resentencing. None of these cases provide sufficient narrowing. In Richmond, the defendant claimed that the F(6) factor was imprecise and indefinite, but, because the court upheld the sentence on the basis of another aggravating factor, the court did not reach the issue. In Blazak, the court upheld the F(6) factor but did not explain why. In Watson, the court reversed a finding of "cruel, heinous or depraved" where the killing was part of a shoot out, but again did not set forth a standard for differentiating between murder that meets the standard and murder that does not. In Ceja, 115 Ariz. 413, 565 P.2d 1274, the court affirmed Ceja’s first death sentence, concluding that the facts of Ceja’s killing reflected a " 'shockingly evil' state of mind 'marked by debasement’ ’’-the dictionary definitions of the words. Id. 565 P.2d at 1278. The decision notes the additional violence imposed by Ceja. The court does not hold that "heinousness or depravity” requires additional violence above and beyond that necessary to kill the victim and then direct the trial court to apply this narrowing construction, however. Rather, the court sets forth the reasons it believes Ceja’s crime was heinous and depraved. This does not provide sufficient guidance for the sentencer. It was not until years later that the court relied on the facts of Ceja's case and others to formulate five factors for the sentencer to consider in determining whether a killing was heinous or depraved. See State v. Gretzler, 135 Ariz. 42, 659 P.2d 1, 11 (1983).
. Thus, the case is distinguishable from Woratzeck v. Stewart, 97 F.3d 329 (9th Cir.1996) (concluding that the F(6) factor had been adequately narrowed and applied by the Arizona Supreme Court in December 17, 1982 when the Court affirmed Woratzeck’s sentence). While the Wor-atzeck panel applied the date the Arizona Supreme Court affirmed Woratzeck's sentence, presumably because the Court performed a new sentencing calculus, I would apply the date the trial court resentenced Ceja, because the Arizona Supreme Court did not perform a new sentencing calculus on appeal. Also, I note that Worat-zeck's sentence was imposed two years after Ceja’s and that his conviction was affirmed three years after Ceja's conviction was affirmed. That the F(6) factor was sufficiently narrowed at the time Woratzeck’s sentence was affirmed does not control whether the F(6) factor was sufficiently narrowed five years earlier when Ceja was sentenced, or three years earlier when Ceja's sentence was affirmed.
. Moran v. Godinez, 40 F.3d 1567 (9th Cir.), amended, 57 F.3d 690 (9th Cir.1994), cert denied, — U.S. -, 116 S.Ct. 479, 133 L.Ed.2d 407 (1995) is not to the contrary. There, the question was whether Nevada created a protected liberty interest by requiring the state to demonstrate that a defendant was competent when he changed his plea to guilty. We held only that, in that particular instance, the violation of Nevada law did not result in the deprivation of a substantive right. In other cases, such as Fetterly and Campbell, we have found sentencing procedures to create protected liberty interests.
. I disagree with the majority’s reasoning in two additional respects that do not affect the result. First, the fact that Ceja was convicted without admission of the photographs in his first trial in no way resolves the question whether admission of the photographs in the second trial violated his constitutional rights. The first conviction was reversed because of prejudicial error in permitting hearsay testimony; it thus cannot be relied on for the conclusion that Ceja would have been convicted anyway even without introduction of the photographs. Nevertheless, I would affirm the conviction because the introduction of the photographs did not make the trial "fundamentally unfair." Batchelor v. Cupp, 693 F.2d 859, 865 (9th Cir.1982) (finding no error in trial court's admission of photographs of victim’s body), cert. denied, 463 U.S. 1212, 103 S.Ct. 3547, 77 L.Ed.2d 1395 (1983).
Second, because of the principle that we may address an issue not raised in the opening brief or in the district court if it "arises while the appeal is pending because of a change in law,” *1261see Gates v. Deukmejian, 987 F.2d 1392, 1408 (9th Cir.1992), I would address Ceja’s fortieth claim, that additional mitigation established since sentencing requires resentencing. Even if we address this claim, however, it is without merit. The case Ceja cites for this proposition. State v. Richmond, simply acknowledges the possibility that a defendant would be entitled to present new evidence of mitigation if his case is remanded to the trial court for a new sentencing hearing. 886 P.2d at 1337. Nowhere does the opinion suggest that mitigation developed after sentencing by itself provides grounds for a new sentencing hearing.