PUBLISH
UNITED STATES CO URT OF APPEALS
FOR THE TENTH CIRCUIT

____________________ ________________ DANA ALIX ZZYYM,
Pl aintiff - Appellee,

v. MICHAEL R. POMPEO in his official capacity as the Secretary of State; STEVEN J. MULLEN, in his official capacity as the Director of the Colorado Passport Agency for the United States Department of State,
De fendants - Appellants. No. 18-1453

____________________ ________________ Appeal from the United States District Court for the District of Colorado (D.C. No. 1: 15-CV-02362-RBJ)

____________________ ________________ Paul D. Castillo, Lambda Legal Defense and Educa tion Fund, Inc., Dallas, Texas (Puneet Cheema, Lambda Legal Defense and Education Fund, Inc., Washington, DC; Emily E. Chow and Rory F. Collins, Faegre Baker Daniels LLP, Minneapolis, Minnesota; and Ann E. Prouty, Faegre Baker Daniels LLP, Denver, Colora do, with him on the brie fs) on behalf of the Plaintiff-Appellee. Jennifer B. Dickey, Deputy Associate Attorney General, United States Department of Justice, Washington, D.C. (Joseph H. Hunt, Assistant Attorney General; Jason R. Dunn, Un ited States Attorney; Hashim M. Mooppan, Deputy A ssistant Attorney General; Brinton Lucas, Counsel to the Assistant Atto rney General; Mark B. St ern and Lewis S. Yelin, FILED United States Court of Appeals Tenth Circuit 

### May 12, 2020 Christopher M. Wolpert Clerk of Court2 Attorneys, Appellate Sta ff, United States Departme nt of Justice, on the briefs) for the Defe ndants-Appellants.

____________________ ________________ Before BACHARACH , SEYMOUR , and McHUGH , Circuit Judges.

____________________ ________________ BACHARACH , Circuit Judge.

____________________ ________________ United States citizen s ordinarily need a passpo rt to leave or reenter the country. 8 U.S.C. § 1185(b). The passport se rves a dual function, proving both identity and allegiance to the United States. Haig v. Agee , 453 U.S. 280, 293 (1981). For decades, the State Department has identified applicants based on characteristics like an indi vidual’s sex. In identifying an applicant’s sex, the State Department has taken a bina ry approach, considering everyone as either male or female. This approach has thwarted Dana Zzyym’s ability to get a passport. Zzyym applied for a U.S. passport, but was intersex and could not accurately identify as either male or female. Because neither option applied, Zzyym requested a passport wi th an “X” designa tion for the sex. The State Department refused and de nied Zzyym’s application. Zzyym sued, alleging that reliance on the binary sex policy

 exceeded the State Department ’s statutory authority,

 was arbitrary and capricious under the Administrative Procedure Act, and3  violated the U.S. Constitution. The district court concluded as a matter of law that the State Department had violated the Admini strative Procedur e Act because

 adherence to the binary sex policy exceeded the State Department’s statutory authority and

 application of the policy to Zzyym was arbitrary and capricious. The court thus did not reach Zz yym’s constitutional claims. We conclude that the State Departme nt acted within its authority but exercised this authority in an arbitrary and capricious manner. The State Department gave five reasons for de nying Zzyym’s request for a passport. Two of the reasons were supported by the ad ministrative record, but three others weren’t. Given the State Depa rtment’s partial reliance on three unsupported reasons, we don’t know whether the St ate Department would have denied Zzyym’ s request if limited to th e two supported reasons. The district court thus should have re manded to the State Department to reconsider the policy based only on the two re asons support ed by the record.
I. Dana Zzyym, an int ersex person, applies for a passport. The State Department defines an in tersex individual as “someone ‘born with reproductive or sexual anatomy and/or ch romosomal pattern that does not fit typical defi nitions of male or fema le.’” Appellants’ Opening Br. at 4–5 (quoting Appellants’ App’x vo l. 1, at 94). This definition fits4 Zzyym, who was born with both male and female genitalia. Given the presence of genitalia for both sexes, Zzyym’s birt h certificate was initially left blank for the sex designation. Bu t Zzyym’s parents decided to raise Zzyym as a male, so the original birt h certificate’s blank for sex was filled in as “male.” The State De partment has treated this birth certificate as the original. Zzyym lived as a male until adult hood. As an adult, Zzyym explored living as a woman and obta ined a driver’s license identifying as female. But Zzyym grew increasingly uncomfortable living as a woman and eventually identified as a nonbinary intersex person. While iden tifying as intersex, Zzyym obtained an amended birth certifi cate identifying the sex
as “UnKnown.” When applying for a passport, Zzyym under stood the need for accuracy. So rather than check the box for male or fe male, Zzyym wrote “intersex.” To support th e identification as inte rsex, Zzyym supplied

 a letter requesting an “X ” sex designation and

 a letter from a physician statin g that Zzyym is intersex. Zzyym also provided the State Department with the amended birth certificate identifying the sex as “UnKnown” and a Colorado driver’s license identifying the sex as female. 1

1 After applying for an intersex passport, Zzyy m obtained a driver’s license identifying the sex as “X.”5 II. The State Department denies Zz yym’s passport application. The State Department denied Zzyym’s request to desi gnate the sex as “X,” explaining that every applicant needed to check the box for either male or female. The State Departme nt offered Zzyym three options:
1. Zzyym could obtain a passport identifying the sex as female, consistent with the driver’s license.
2. Zzyym could obtain a pa ssport identify ing the sex as male if a physician attested th at Zzyym had transitioned to become a male.
3. Zzyym could withdraw the application. Zzyym declined these options a nd requested reconsideration, providing two more physici ans’ letters stating that Zzyym is intersex. The State Department declined to reco nsider and again denied Zzyym’s application based on the binary consider ation of everyone as either male or female.
III. Zzyym sues the St ate Department. Zzyym sued and the district court ordered a remand, concluding that the State Department’s denial of Zzyym’s application was arbitrary and capricious. On remand, the State Department decide d to retain its policy and again denied Zzyym’s applicatio n for a passport with an “X” sex designation. The district court again concluded that the State Department6 had violated the Administrative Procedure Act, and the government appeals. IV. The State Department acted within its statutory authority. The district court concluded that the State Department had exceeded its statutory authority by enforcing its binary sex policy against Zzyym. The government disputes this conclusi on, and Zzyym presents two arguments in rebuttal:
1. The government waived this i ssue by omitting it from the opening appellate brief.
2. The State Department lacked statutory authority to deny a passport application based on a refusal to check either the “male” or “female” box. We conclude that (1) th e government did not waive this issue and (2) the State Department had statut ory authority to require applicants to identify their sex as male or female. A. Standard of Review We conduct de novo review of the di strict court’s determination of the State Department’s statutory authority. EnergySolutions, LLC v. Utah , 625 F.3d 1261, 1271 (10th Cir. 2010). If the Stat e Department lacked statutory authorit y, its decision must be set aside. 5 U.S.C. § 706(2)(C).
B. The State Department did not waive this argument.

In its opening appella te brief, the governm ent focused largely on whether the State Department had acted arbitrarily and capriciously by7 relying on the bina ry sex policy. Bu t the government’s opening appellate brief also addressed the issue of statut ory authority, arguing that reversal of the characterization as arbitrary and capricious would compel us to reverse the ruling on st atutory authority. The gov ernment reas oned that “the court’s statut ory-authority holding [was] entirely parasitic on its arbitrary-and-capricious ruling and therefore fail[ed] for the same reasons.” Appellants’ Opening Br. at 29. Zzyym characterizes this reasoning as perfunctory, emphasizing that the government did not iden tify an issue i nvolving statutor y authority or address the issue elsewh ere in its brief. Ac cording to Zzyym, the government’s perfunctory re asoning constituted a wa iver of any challenge to the State Department’s statutory authority. We disagree. In our view, the gover nment’s opening appella te brief adequately addressed the issue of st atutory authority. Though on ly one appellate issue was identified, th e government argued that the State Department had good reason to deny Zz yym’s passport application. The government apparently intended that analys is to address both of the district court’s rulings. This approach was reasonable because the district court had intertwined its rulings on Zzyym’s arguments. See Prieto v. Quarterman , 456 F.3d 511, 517 (5th Ci r. 2006) (stating that when procedural and substantive issues were “inextricably intertwined,” the appellant did not8 waive the procedural issue by briefi ng only the substantive issue). The district court concluded that

 the State Department’s reas ons had been arbitrary and capricious and

 the absence of good r easons meant that th e State Department had exceeded its statutory authority. Zzyym v. Pompeo , 341 F. Supp. 3d 1248, 1260 (D. Colo. 2018). Both rulings rested on the State De partment’s failure to justify its reliance on the binary sex policy. See id. (“Because neithe r the Passport Act nor any other law authorizes th e denial of a passport application without good reason, and adherence to a series of internal policies that do not contemplate the existence of inte rsex people is no t good reason, the Department has acted in excess of its statutory jurisdicti on.”). We thus conclude that the gover nment adequately briefe d its challenge as to statutory authority. Given this conclu sion, we reject Zz yym’s allegation of waiver. C. The State Department had st atutory authority to deny Zzyym’s passport application base d on the binary sex policy. The Passport Act allows the Secret ary of State to “grant and issue passports, and cause passpor ts to be granted, issued, and verified in foreign countries . . . under su ch rules as the Presid ent shall designate and prescribe for and on behalf of the Un ited States and no other person shall grant, issue, or verify such passpor ts.” 22 U.S.C. § 211a. In turn, the9 President has delegated the authority to prescribe rules to the Secretary of State. Executive Order 11295, 31 Fed. Reg. 10,603 (Aug. 5, 1966). We must consider the scope of statutory authority delegated to the Secretary of State and the State Department. The statutory language is perm issive, authorizing the State Department to deny passports for reasons not listed in the Act. Haig v. Agee , 453 U.S. 280, 290 (1981). For exampl e, the Act does not say whether the State Department can deny passports to app licants unwilling to state their birth dates or Social Security numbers. Despite th e absence of an express statutory provision, few would question the State Department’s authority to deny passports when applicants withho ld their birth dates or Social Security numbers. See 22 C.F.R. § 51.20(b) (requ iring applicants to answer all questions pe rtaining to eligibil ity for a passport). The Passport Act is silent about th e State Department ’s authority to deny a passport to applicants who do no t identify as male or fema le. Given this silence, Zzyym disputes the Stat e Department’s statutory authority to deny a passport to an ap plicant unwilling to check the box for either male or female. The Supreme Court has addressed other challenges to the State Department’s authority to deny passports fo r reasons that are not listed in the Passport Act. In these cases, th e Supreme Court has analyzed the State Department’s statutory authority by considering past administrative10 practice and congressional acquiescence. See, e.g. , Kent v. Dulles , 357 U.S. 116, 127–30 (1958); Zemel v. Rusk , 381 U.S. 1, 7–13 (1965); Haig v. Agee , 453 U.S. 280, 291–301 (1981). The Supreme Court first relied on past administrative practice in Kent v. Dulles , 357 U.S. 116 (1958). There the government insisted that applicants disclaim membership in th e Communist Party in order to qualify for passports. 357 U.S. at 117–20. When some applic ants refused, the State Department declined to consider their applications. Id. at 119–20. The Supreme Court held that the State Departme nt had exceeded its statutory authority. Id. at 129–30. In reaching th is holding, the Court observed that the State Department had previously denied passports based on citizenship, allegian ce to the Unit ed States, or unlawful conduct. Id. at 127. By contrast, the State Department had inconsistently denied passports based on belief or association. Id. at 129–30. This inconsistency made it unlikely that Congress ha d acquiesced in denying passports based on an applicant’s membership in the Communist Party. Id. But when the State Department has consistently restricted passports, courts assume that Congre ss has acquiesced if it ha s not legislated on the subject. For example, in Zemel v. Rusk , the Supreme Cour t held that the State Department could refuse to valida te passports for tr avel to Cuba. 381 U.S. 1, 3 (1965). The Court reasoned that the Passport Act’s language was broad enough to pe rmit restrictions on where the applicant could go,11 emphasizing the State Department’s history of restricting destinations. Id.

at 8–12. But the State Department must sometimes confront novel challenges. Without past opportunitie s to enforce a policy, the State Department’s open assertion of authority imp lies congressiona l acquiescence. Haig v. Agee , 453 U.S. 280, 303 (1981). The Supreme Court inferred such congressional acquiescence in Haig v. Agee , 453 U.S. 280 (1981). There the State Department revoked the passport of a former CIA officer who had exposed undercover CIA operatives while travelli ng abroad. 453 U.S. at 283–86. In the past, the State Department had rarely encounter ed the need to revoke a passport based on national securi ty or foreign policy. Id. at 303. But the infrequency of previous challenges didn’t matter; the Court reasoned that the State Department had “openly asse rted” its power to revoke a passport for reasons involving nati onal security and foreign policy and Congress had not stepped in. Id. at 303–06 (quoting Zemel , 381 U.S. at 9). The Court thus concluded that Congress had implicitly approved the State Department’s exercise of statutory power. Id. at 306. So th e Court upheld the State Department’s re vocation of the passport. Id. Agee ’s logic fits here. Prior to Zzyym’s application, the State Department had never denied a pa ssport based on an applicant’s unwillingness to identi fy as male or female. But under Agee , the12 infrequency of enforcem ent does not strip the State Department of statutory authority. In denying a pass port to Zzyym , the State Department followed a binary se x policy that had been in place for roughly 39 years. Zzyym argues that th e passport applicati on itself did not alert Congress to the State Depa rtment’s policy. But the binary sex policy was hardly a secret, for the State Departme nt had enacted regulations requiring every applicant to use par ticular forms and to answ er all of the questions on those forms. 22 C.F.R. § 51.20(a)–(b). Congress could have said if it wanted to allow applicants to bypass certain questions. Gi ven the longevity of the State Department’s policy and Congress’s apparent acquiescence, we conclude that the binary sex policy fell within the State Department’s statutory authority. 2 Despite Congress’s apparent acquies cence, Zzyym contends that the State Department can deny passports only for the reasons identified in
Kent , Zemel , and Agee : citizenship, allegiance, unlawful conduct, foreign policy, and national security. See pp. 9–11, above. We disagree. Though

2 The district court concluded that the State Department had exceeded its authority because fede ral law does not permit denial of a passport application “without good reason.” Zzyym v. Pompeo , 341 F. Supp. 3d 1248, 1260 (D. Colo . 2018). We view the qualit y of the reasons as pertinent to Zzyym’s cl aim that the State Depa rtment’s reasoning was arbitrary and capricious. See Part V, below. The issue of statutory authority turns on past administrative practice and congressional acquiescence—not the qua lity of the State Depa rtment’s reasoning. See pp. 9–10, above.13 the Supreme Court has crystallized some lawful and un lawful justifications for denying a passport, th ese justifications are ill ustrative—not exhaustive. The Supreme Court addresse d them only because they were at issue in the three cases. See , e.g. , Kent , 357 U.S. at 127–28 (focusing only on established reasons for denying a pass port that are “mat erial here”). The Supreme Court didn’t suggest that th ese were the only r easons that could justify denial of a passport. We thus conclude that th e State Department had statutory authority to deny a passpo rt to Zzyym for failing to identify as a male or female. V. The State Depart ment’s reliance on its binary sex policy was arbitrary and capricious. The resulting issue is whether this application of the binary sex policy was arbitrar y and capricious based on the existing administrative record. See 5 U.S.C. § 706(2)(A) (arbitrar y-and-capricious standard); Copar Pumice Co. v. Tidwell , 603 F.3d 780, 791 n. 3 (10th Cir. 2010) (existing administrative record). For this inquiry, we presume that the policy was valid and place th e burden of pr oof on Zzyym. W. Watersheds Project v. Bureau of Land Mgmt. , 721 F.3d 1264, 1273 (1 0th Cir. 2013). Our review is “narrow,” and we are “not to substitute [our] judgment” for the St ate Department’s. Motor Vehicle Mfrs. Ass’n of U.S.,
Inc. v. State Farm Mut. Auto. Ins. Co. , 463 U.S. 29, 43 (1983). Given the narrowness of our review, we will dist urb the administrative action only if14 the State Department relied on improper factors, disregarded an important aspect of the problem, provided an explanation that was implausible or inconsistent with the evidence, or failed to consider an appropriate alternative. Id. at 43, 51. On appeal, the governme nt defends its reason s for requiring Zzyym to identify as a ma le or female. A. Only two of the State Department’s five reasons are supported by the administrative record. The State Department gave five reasons for relying on the binary sex policy:
1. The policy ensured the accuracy and re liability of U.S. passports.
2. The policy helped identify indivi duals ineligible for passports.
3. The policy helped make passport data useful for other agencies.
4. No medical consensus existed on how to determine whether someone was intersex.
5. Creating a third designation fo r sex (“X”) was not feasible. We conclude that the first, fourth, and fifth reasons la ck record support, but the second and third reasons are supported. 1. The State Depart ment’s first reason (that the binary sex policy ensured the accuracy and reliability of U.S. passports) lacks support in the record. The State Department justified the bi nary sex policy in part as a way to promote accuracy and reliability, re asoning that every U.S. jurisdiction15 had identified all citizens as either male or female . For this justification, the State Department focused on how it dete rmines eligibility for passports. This determination ordinari ly requires the St ate Department to verify an applicant’s identity through identifica tion documents issued by other U.S. jurisdictions. So the St ate Department considered how those jurisdictions identify characteristics such as an individual’s sex. The State Department noted that many U.S. jurisdictions allow amendment of identif ication documents, but diff er on when to allow an amendment. For example, if a male transitions to a female, different jurisdictions may vary in

 whether to allow amendment of a birth certificate to reflect the new sex and

 what evidence is required to obtain the amendment. Given these differences, the State De partment focuses only on original identification documents. 3 We thus consider how U.S. jurisdic tions have treated a citizen’s sex in original identif ication documents. For this inquiry, we us e May 2017 as the applicable time frame because that is when the State Department denied Zzyym’s request. See p. 13, above.

3 Zzyym has not challe nged the State Department’s policy of relying only on original identification documents wh en evaluating passport applications.16 In May 2017, every U.S. jurisdiction used a bi nary sex policy in a citizen’s original id entification document s, always listing the sex as either male or female. 4 Given the prevalen ce of binary sex policies, the State Department reasoned that listing a se x other than male or female would hamper verification of an applicant’s identity. Zzyym argues that re quiring consistency between inaccurate identification documents doe s not render th em more accurate or reliable. We agree. And for intersex indi viduals like Zzyym , treating every applicant as male or female woul d necessarily create inaccuracies.

4 Zzyym argues that the agency fa iled to consider recent efforts by some states to authorize amended documents recogniz ing a third sex, characterizing these efforts as a tr end toward allowi ng a third sex designation. But the State Department did consider this development, acknowledging that by 2017 a handful of jurisdictio ns had “iss ued amended birth certificates in a third sex, and . . . a very few number of state courts [had] issued court orders recognizing a sex change to a sex other than male or female.” Appellants’ App’x vol. 1, at 84. Desp ite these developments, the State Department continued to rely on original docum ents and resist acceptance of amended documents. Zzyym also points ou t that state policies have evolved since May 2017. For example, Zz yym says that

 twelve states and the District of Columbia now authorize sex designations other than “M” or “F” on identification documents and

 seven states allow a gender -neutral category on birth certificates. But we cannot consid er this information because we are limited to the administrative record as of May 2017. See p. 13, above.17 The State Department ac knowledges that some individuals are born neither male nor female. Forcing thes e individuals to pi ck a gender thus injects inaccuracy into th e data. A chef might label a jar of salt a jar of sugar, but the labe l does not make the salt an y sweeter. Nor does requiring intersex people to mark “male” or “female” on an application make the passport any more accurate. But the State Department prizes accuracy. To promote accuracy, the State Department requires applicants to submit original birth certificates, 22 C.F.R. § 51.42, and establish identity with corroborating identification documents, 22 C.F.R. § 51.23. If the designated se x does not match the identification documents, the applicant must obta in medical certification by a licensed physician. 7 FAM § 1310(a ) App. M; Appellants’ App’x vol. 1, at 88. Given these requirements, an inters ex applicant like Zzyym could not accurately complete the pa ssport application in May 2017. If the applicant was intersex, the original identifi cation documents would not accurately identify the applicant’s sex. So the St ate Department’s re liance on original identification documents wo uld prevent intersex applicants from accurately identifying their sex. At oral argument, the State Depart ment conceded that applications for intersex indivi duals like Zzyym wo uld be less accurate under the binary sex policy. The State Department thus noted that it had offered to produce18 a passport with an “F ” (matching Zzyym’s original Colorado driver’s license) or an “M” (matching the or iginal birth certif icate). But when asked what an applicant li ke Zzyym should do to ensure the accuracy of the passport, counsel for the State Department acknowle dged that (1) “it may be difficult when one is confronted wi th a form with limited options that may not track one’s best an swer to a question” and (2) applicants “have to choose what fits best, an d that may not be the most accura te answer that they would like to pr ovide, but it is the answer th at is available.” Oral Arg. at 7:39–8:25. In many cases, however , the “best” availa ble answer may not conform to the applicant’s original id entity documents. States issue most original identification documents; an d when the State Department denied Zzyym’s application, most state identification docu ments pigeonholed everyone as male or fema le even though some pe ople are neither. So reliance on the original identificat ion documents would sometimes create inaccurate in formation. Zzyym’s experience illustrates the inevitable inaccuracies of a binary sex policy. Zzyym had two original identification documents that would ordinarily establish the sex: The original birth certificate identified Zzyym as male, and the driver’s licens e said female. With conflicting identification documents, the State Depa rtment instructed Zzyym to either identify as female or obtain a medical cer tification showing transition to19 male. Appellants’ App’x vol. 1, at 67–68 . But this instruct ion didn’t make sense because Zzyym hadn’t transiti oned from female to male, and Zzyym’s original birth certificat e said that Zzyym was male. The State Department’s policy effectively allo wed Zzyym to obtain a passport by claiming to be either male or female. But the State Department’s binary sex policy assu mes that Zzyym must be one or the other. How could Zzyym be neither male nor female and accurately identify as either sex? Given the State Department’s willi ngness to allow Zz yym to identify as either male or female, the binary sex policy sunder s the accuracy and reliability of inform ation on Zzyym’s passport application.
* * * The State Department la cks record support for its asserted interest in accuracy and reliability. The State De partment mirrored how every U.S. jurisdiction was treating gender in May 2017, but these jurisdictions shoehorned everyone into a binary sex classification ill-su ited for intersex applicants. The State Department thus relied on informa tion that didn’t accurately describe intersex applicants like Zzyym.20 2. The State Depart ment’s second reason (that the binary sex policy helped the State Depart ment identify individuals ineligible for passports) is supported by the record. The State Department also explained that the binary sex policy helpfully matches how other federal ag encies record some one’s sex. This explanation is suppo rted by th e record. The State Department denies pa ssport applications for various

reasons. See 22 C.F.R. §§ 51.60–51 .62. To evaluate th ese applications, the State Department must gather a broad range of informatio n from federal, state, and local authoritie s. For example, the State Department may need to collect information from other federal agencies to decide whether an applicant has defaulted on a federal loan (22 C.F.R. § 51.60(a)(1)), has committed a sex offense (2 2 C.F.R. § 51.60(g)), or has obtained a conviction for drug traffick ing (22 C.F.R. § 51.61). The State Department thus underscor ed two facts bear ing on the need for consistency in da ta recorded by different federal agencies:
1. “Sex is one of th e primary data points used by these agencies in recordkeeping . . . .” Appellants’ App’x vol. 1, at 85; see id. at 45–46 (“Sex is a key co mponent of the ‘biometric id entity’ that the Department uses to verify the identity of th e applicant and distinguish individuals.”).
2. “[A]ll such agencies re cognize only two sexes.” Id. at 85. In May 2017, the State De partment’s system requ ired an applicant’s data to match many other federal agencies. And every federal database identified each person as either male or female. So if the State Department21 searched for Zzyym with an “X” desi gnation for sex, the search would yield mismatches for the applicant’s sex. To uncover th e reason for the mismatches, an employee in the State Department would need to manually override the “X” designation of sex. The State Department could thus rationally insist on identifying the applicant’s sex in a way that matched other federal databases. 5 To minimize confusion, the State Department reason ably concluded that a binary sex policy could enhance the ability to verify identity. 6 Of course, the State Department also sear ches state and local databases in order to a ssess eligibility for a passpor t. For example, federal

5 Zzyym contends that the State De partment failed to consider the federal government’s permi ssion for foreign individuals to enter the United States with passports bearing an “X ” designation for sex. But the State Department could reasonably distinguish between the difficulties in accepting a foreign passport and issu ing a U.S. passport. Accepting a foreign passport may not implicate th e depth of communi cation with other federal databases that is needed to ensure eligibility for a U.S. passport. And we must defer to an agency’s “reasonable conclusions regarding ‘technical or scientific matters within the agency ’s area of expertise.’” Utah Envtl. Cong. v. Richmond , 483 F.3d 1127, 1140 (10th Cir. 2007) (quoting Utah Envtl. Cong. v. Dale Bosworth , 443 F.3d 732, 739 (10th Cir. 2006)).

6 Zzyym argues that mismatches “may in fact aid” the State Department because “[a]ny mismatch is flagged—whether an M/F or X/M/F disparity—ensuring that the underlying application receives more scrutiny.” Appellee’s Re sp. Br. at 34. But Zzyym cites no authority or evidence for this proposition. Without any au thority or evidence, we decline to speculate on the possibility that more mismatch es could aid the State Department.22 law prohibits the is suance of passports to a nyone owing more than $2,500 in back child suppo rt. 42 U.S.C. § 652(k); 22 C.F.R. § 51.60( a)(2). Child support is governed by state law and en forced by st ate and local agencies. Though some state agencies did acco mmodate a third se x designation in 2017, the State Department reasonably concluded that inaccuracies could still arise when contrastin g an “X” sex designatio n with the more common methods of designati ng someone’s sex. Zzyym points out that the State De partment could obtain useable information from other agen cies despite differences in the ways that they identified an individual’s sex. For ex ample, if an app licant’s sex didn’t match a federal agency’s records, th e State Department could verify an applicant’s social security number, da te of birth, and name. But manually overriding the mi smatches would require ad ditional resources. Zzyym also points out that the State Department was apparently willing to tolerate mismatches for transgender individuals. For these individuals, the State Department used a process allowing an applicant to identify a sex differing fr om the one on the driver’s license or birth certificate. Zzyym questions why th e State Department was willing to accept mismatches fo r transgender applicants but not intersex applicants. This argument proves that the State Departme nt could accommodate discrepancies—not that it had to do so. In adopting the tr ansgender policy, the State Department n eeded to evaluate a ll pertinent factors. Citizens to23 Pres. Overton Park , Inc. v. Volpe , 401 U.S. 402, 416 (1971 ). But we have little information on the mix of factors cont ributing to the State Department’s policy for transgender ap plicants. For example, nothing in the record suggests wh ether the State Department considered the possibility of mismatches with state da tabases as a factor weighing against the transgender policy. Regardless of what the pertinent f actors were, we know that the State Department was ultimately willing to tolerate some mismatches between transgender applicants’ passport appli cations and the original identification documents. But we don’t know how the State De partment weighed the inevitability of these mismatches. Given the ab sence of information on how the State Department weighed this factor for transgender applicants, we cannot speculate. So the State Department’s ap parent tolerance for mismatches among transgender appl icants does no t bear on the reasonableness of this fact or for intersex applicants. Transgender applicants aside, Zzyy m points out that mismatches may emerge whenever th e State Department and a par ticular state use different methods to identify an individual’s se x. For example, Zz yym points to the instruction to identify as either ma le or female, which may or may not correspond to states’ unde rlying databases. So under either approach, mismatches will arise.24 But the State Department has reasonably tried to limit unnecessary mismatches. Under arbitrary-and-capric ious review, the agency need not select a perfect soluti on—just a rational one. See Forest Guar dians v. U.S.
Forest Serv. , 329 F.3d 1089, 1099 (9th Cir. 2003) (“An agency’s actions need not be perfect; we ma y only set aside decisions that have no basis in fact, and not those with which we disagree.”), quoted with approval in Biodiversity Conservation All. v. Jiron , 762 F.3d 1036, 1074 (10th Cir. 2014). Because the State Department could rati onally try to reduce unnecessary mismatches, we conclude that the administrative record supports the State Departme nt’s second reason to re ly on the binary sex policy. 3. The State Depart ment’s third reason (t hat the binary sex policy helped make passport da ta useful for other agencies) is supported by the record. The State Department al so reasoned that using a third sex designation could burden other state and federal agencies when th ey use the State Department’s data. Again, the State Department noted that (1) most agencies’ systems accommodate only two sexes and (2) allowing a third sex designation could complicate sear ches. These compli cations, the State Department reasoned, woul d burden other agencies that use passport data.25 For example, the State Department pointed to law enforcement, which often uses passport data to identify vi ctims and to locate cr iminal suspects. Zzyym argues that the State Department’s ra tionale lacks record support and relies on “sw eeping assumptions about te chnical specifications of third-party computer systems.” Appellee’s Resp. Br. at 34. We disagree. The State Department could reasonably conclude that us e of a third sex designation would impede at least some other systems that classify everyone as either male or fema le. We thus conclude that the administrative record suppor ted the State Department’s third reason to rely on the binary sex policy. 4. The State Department’s fourth reason (that a lack of medical consensus existed on how to identify individuals as intersex) is unsupport ed by the record. The State Department also concluded that the medical community lacks a consensus on how to determ ine whether someon e is intersex, rendering an “X” designation “unrelia ble as a componen t of identity.” Appellants’ App’x vol. 1, at 86. But this reason ing lacks support in the administrative record and does not apply to unquesti onably intersex individuals like Zzyym. According to the State Department, medical experts vary on whether to base intersexuality so lely on somatic characteris tics, self-identification as intersex, or both. But the State Depa rtment cites no sc ientific evidence of this disagreement a bout the medical definition of intersexuality.26 In defending this rationale, the St ate Department cites pages 86 and 87 of its appendix. This page is simply an excerpt from the State Department’s brief in district court. In that brief, the State Department failed to cite any eviden tiary support for a disagr eement in the medical community about the meaning of intersexuality. 7 Indeed, the State Department’s appe llate brief defines intersexuality based on somatic characteristics, st ating that an intersex person is “someone ‘born with re productive or sexual anat omy and/or chromosomal pattern that does not fit typical de finitions of male or female.’” Appellants’ Opening Br. at 4 (citing Appe llants’ App’x vol. 1, at 94). This definition appears consistent wi th the academic literature on intersexuality. 8

7 In denying Zzyym’s re quest, the State Departme nt said that “[r]eview of recent expert declarat ions and medical literature confirms that there is no [] consensus at this ti me as to the definition of a third sex.” Appellants’ App’x vol. 1, at 86. But the State De partment did not identify or submit any of these declarations or medical excerpts.

8 See Heino F.L. Meyer-Bahlburg, Transsexualism (“Gender Identity Disorder”) – A CNS-Limited Form of Intersexuality? , in Hormonal and Genetic Basis of Sexual Differentiation Disord ers and Hot Topics in Endocrinology 75, 75–77 (M aria I. New & Joe Le igh Simpson eds., 2010) (describing intersexuality as “somatic ” and distinguishing gender identity disorder from intersexualit y); I.A. Hughes et al., Consensus Statement on Management of In tersex Disorders , 91 Archives Di sease Childhood 554, 554–56 (2006) (surveying fifty international experts in the field of intersex disorders and stating that criteria suggesting a disorder of sexual development include genita l ambiguity or variations, a family history of disorders of sexual development, and chromosomal variations); John27 In district court, the State De partment pointed out that three physicians had given thr ee different reasons for classifying Zzyym as intersex:
1. Zzyym “was born with ambi guous genitalia.” Appellants’ App’x vol. 1, at 59.
2. Zzyym “has had the appropriate cl inical treatment for transition to intersex.” Id. at 71.
3. Zzyym “was born inters ex,” “identifies as intersex,” and “has had surgery for transition to female genitalia.” Id. at 73. These differences, the State Department argued, illustrated the lack of medical consensus about the meaning of intersexuality. The State Department’s argument in district court had overlooked the context for these differences. The firs t physician had cla ssified Zzyym as intersex based sole ly on the basis of somatic characteristics, referring to

McLean Morris, Intersexuality , 163 J. Am. Med. Ass’n 538, 540 (1957) (stating that the term “i ntersexual” “should be re stricted to those with congenital anatomic variations and not used when referring to those showing the endocrine phenomena of post-natal virilization or feminization”); U.S. National Library of Medicine, Intersex , MedlinePlus, https://medlineplus.gov/ency/article /001669.htm (updated Aug. 7, 2019) (“Intersex is a group of conditions where there is a discrepancy between the external genitals and the internal genitals (the testes and ovaries).”); see also Jessica A. Clarke, They, Them, and Theirs , 132 Harv. L. Rev. 894, 898 (2019) (stating that intersex indi viduals are “people who are born with any of a range of sex characteristics that may not fit a doctor’s notions of binary ‘male’ or ‘female’ bodies” (quo ting Intersex Defi nitions, Interact, https://interactadvocates.org/interse x-definitions/)); Aileen Kennedy, Fixed at Birth: Medical and Legal Erasures of Intersex Variations , 39 Univ. New S. Wales L.J. 813, 813 (2016 ) (“The term ‘intersex’ describes variations in sex development whereby a person’s biological sex traits are not exclusively male or female .” (footnote omitted)).28 the presence of ambiguous genitalia. Th e State Department rejected this explanation and pointed Zzyym to the policy for transgender applicants, which required a physician’s statement attesting to “appropriate clinical treatment for transition to the new gender.” Id. at 68. In re sponse, Zzyym supplied the second letter, which complied with the State Department’s instruction to verify tran sition to the new gender. Id. at 71. The third letter simply confirmed that Zzyym was in tersex and identified as intersex. Id . at 73. None of the letters purported to de fine intersexuality or discussed how the medical community de fines intersexuality. Even if the medical community disagreed on whether some individuals are intersex, the State Department would need to explain why the lack of a consensus would justify denying Zzyym’s application. See Burlington Truck Lines, Inc. v. United States , 371 U.S. 156, 168 (1962) (stating that administrati ve decisions must rationally connect the factual findings to th e decision being made). The State Department didn’t provide such an explanation, assuming instead that disagreement about whet her some applicants were intersex would prevent classification of a nyone as intersex. Why? The State Department has never questioned whether Zzyym is intersex. Given Zzyym’s undebatable intersexuality, the State Department failed to explain why a lack of consensus about other individuals would justify forcing intersex individuals like Zzyym to inaccurately id entify themselves as male29 or female. Without such an explanation, we co nclude that the State Department lacked re cord support for its fourth reason to rely on a binary sex classification. 9
5. The State Depart ment’s fifth reason (t hat adding a third sex designation (“X”) would be infe asible) lacks support in the record. Finally, the State Department reasoned that a third sex designation would be infeasible because of the required time and expense. But the

9 Zzyym also argues th at the State Department could have adopted the conclusions of the World Professional Association for Transgender Health (WPATH). After all, WPATH’s c onclusions had sp urred the State Department to revise its policy fo r transgender passport applications. WPATH’s Standards of Care acknow ledge intersexuality and suggest that countries offer a third sex option. Given these standards, Zzyym argues that the State Department should have (1) adhered to the WPATH Standards of Care or (2) explained its departure from those standards. See Encino Motorcars, LLC v. Navarro , 136 S. Ct. 2117, 2126 (2016) (holding that an agency must show an awarenes s that it is changing its policy and explain why). In our view, the State Department was not required to use the WPATH standards for intersex individuals despite using these standards for transgender applicants. WPAT H is a private nonprofit health organization that makes recommenda tions, not a public entity creating international standards for passports. And the State Department’s Foreign Affairs Manual has not establishe d WPATH standards as official government standards or required the gov ernment to defer to WPATH standards in future policymaking. The Foreign Affairs Ma nual states only that the government chos e to use the WPATH sta ndards for individuals transitioning from one sex to another. Adoptin g WPATH’s recommendation for transgender indivi duals does not requir e adoption of the recommendation for inte rsex individuals.30 State Department did not estimate the additional tim e or expense. The State Department said only that it anticipa ted “considerable” challenges to

 alter various systems,

 update systems within the Bur eau of Consular Affairs,

 update internal State Depa rtment systems, and

 update systems within other federal agenci es that rely on passport data. Appellants’ App’x vol. 1, at 87. After the district court grante d judgment to Zz yym, the State Department moved to stay the court’s order. With this motion, the State Department attached a declaration qu antifying the time and expense to alter the passport system. Appellants’ App’x vol. 3, at 229. The declarant

 noted that standard U.S. pass ports are electronic and contain chips with a se cure digitized image and biographic data,

 described many info rmation technology sy stems that would require modification, and

 estimated that changing existing software systems would take 24 months and cost $11 million.
Id. at 225–26. We decline to consider these estimates because “review of agency action ‘generally focuses on the admi nistrative record in existence at the time of the agency’s decision.’” Copar Pumice Co. v. Tidwell , 60331 F.3d 780, 791 n.3 (10t h Cir. 2010) (quoting Forest Guardians v. U.S.
Forest Serv. , 579 F.3d 1114, 1131 (10th Cir. 2009)); see p. 13, above. 10 To justify the la ck of an estimate, the State Department cites Hillsdale Environmen tal Loss Preventi on, Inc. v. U.S. Army Corps of Engineers , 702 F.3d 1156 (10th Cir. 2012). That opinion does not apply. In Hillsdale , we held that the Army Corps had not needed to quantify the effects of granting a permit on certain air em issions because those emissions involved only a small fraction of the anticipated impact. 702 F.3d at 1175–76. Here th e government’s argument is di fferent—that a change would obvious ly increase cost. To assess the governmen t’s allegation of an obvious increase in cost, we must engage in a s earching, careful inquiry. City of Color ado Springs v. Solis , 589 F.3d 1121, 1131 (10th Cir. 2009). In doing so, we cannot accept conclusory statements in lieu of a meaningful explanation. See Zen

10 The State Department also s ubmitted a second d eclaration that discussed consideration of a “one-off” passport. Appellants’ App’x vol. 3, at 227. This declarant ac knowledged the possibility of incorporating “‘onetime’ modifications to cer tain systems to change the sex marker in the issuance system’s data base, to an ‘X.’” Id. Despite this possibility, the State Department ultimat ely decided not to produce a one-off passport because it would undermine the validity of U.S. passports and compromise national security and fore ign policy objectives. Id. But the administrative record contains no mention of con cerns involving nati onal security or foreign policy, so we decline to consider this argument.32 Magnets, LLC v. Consum er Prod. Safety Comm’n , 841 F.3d 1141, 1150 (10th Cir. 2016). The expense is not obvious. Ind eed, nine states (California, Colorado, Maine, Minnesota, Nevada , New Jersey, Oregon, Vermont, and Washington) insist that “adding non-binary gend er designati on in accord with national and international st andards has requir ed negligible administrative effort—the kind that accompanies rout ine changes to government documents.” Br. of Amici Curiae States at 8. One of these states (Colorado) represents that it in curred no cost in adopting a third sex designation. Id. Given the conflicting information and the absence of any cost evidence in the administrative re cord, we do not re gard the additional expense as obvious. In the absence of any meaningful explanation, the State Department lacks record support for its reliance on additional time and expense.
B. The State Department did not fail to consider alternatives. Zzyym insists that the State De partment had to consider the alternative of a third sex designation before deviating fr om international standards. See Motor Vehicle Mfrs. Ass’n of U.S., Inc. v. State Farm Mut.
Auto. Ins. Co. , 463 U.S. 29, 51 (1983). But the Stat e Department did consider those standards, and reliance on the binary sex policy conformed to those standards.33 The International Civil Aviation Organization (ICAO) sets standards to ensure that every c ountry’s passports are mach ine-readable. The State Department followed that policy, ma king every U.S. passport machinereadable. In recognizing gender ch anges and intersex in dividuals, the ICAO noted that some countrie s might issue passports with an “unspecified” designation, using an “X” printed le tter and a “<” machine-readable character. In explaining it s decision to adhere to the binary sex policy, the State Department attached a document ent itled “Use of a Third Sex Marker by Contracting States as Permitted by ICAO.” Appellee’ s Supp. App’x at 56. The attachment of this document showed that the St ate Department had recognized the ICAO change. The binary sex policy conforms to the ICAO standard. The ICAO allowed use of a third se x designation but did not require it. Appellants’ App’x vol. 3, at 220 (“Si nce 1999, ICAO standards have allowed, but do not require, countries to permit a third sex designation: ‘unspecified.’”). The State Department simply decided not to use the ICAO’s option, 11

11 Only a few countries use the ICAO’s “X /<” option even though it has been standardized fo r roughly 20 years. See Appellants’ App’x vol. 3, at 220 (“Although several countr ies have begun to offer a third option in their passports, most c ountries have not.”); Appellee’s Supp. App’x at 57 (listing Australia, Bangla desh, Denmark, India, Malta, Nepal, and New Zealand as the only coun tries issuing passports in 2017 with a third sex designation).34 reasoning that it would not have matc hed how any U.S. jurisdiction was treating the designation of sex in orig inal identificatio n documents. The State Department thus considered th e alternative of using a third sex designation. VI. Given the existence of two reason s that are supported and three others that are unsupported, the State Department must reconsider its denial of Zzyym’s application. We have concluded that (1) the Stat e Department’s fi rst, fourth, and fifth reasons are unsuppo rted and (2) the second and third reasons are supported. We have no way of knowing whether the State Department would still have relied on the binary se x policy if limited to the second and third reasons. When an administrative decision rests on multip le grounds—some supported and some not—we must determine what the agency would have done had it recognized its errors. When an agency has indicated that its reasons were independen t and one of the reasons was flawed, we have upheld the agen cy action. Am. Fed’n of Gov’t Em ps. AFL-CIO, Local 2263 v. Fed. Labor Relations Auth. , 454 F.3d 1101 , 1107 (10th Ci r. 2006). But we have never encounte red a situation where we cannot tell whether the agency would have take n the same action if it had known that some justifications we re unsupported. Two circuits, the D.C. Ci rcuit and the Fifth Circuit, have considered this issue. The D.C. Circuit has he ld that when an agency relies on35 multiple grounds and some of the reas ons are unsupported , the court can ordinarily uphold the admi nistrative decision only if the agen cy clearly would have reac hed the same decision if limi ted to the supported reasons. NLRB v. CNN Am., Inc. , 865 F.3d 740, 756 (D .C. Cir. 2017); Bally’s Park Place, Inc. v. NLRB , 646 F.3d 929, 939 (D.C. Cir. 2011); Casino Airlines, Inc. v. Nat’l Transp. Safety Bd ., 439 F.3d 715, 717 (D.C. Cir. 2006). For this holding, the D.C. Circ uit has reasoned that “[a]rbitrary and capricious review strictly prohib its us from upholding agen cy action based only on our best guess as to what reasoning truly motivated it.” Williams Gas Processing-Gulf Coast Co. v. FERC , 475 F.3d 319, 328–29 (D.C. Cir. 2006). So when th e court cannot tell whether an agency’s surviving rationale would have led to the sa me decision, the D.C. Circuit has remanded to the agency. See, e.g. , Consol. Edison Co. of New York v.
FERC , 823 F.2d 630, 641 (D .C. Cir. 1987). The Fifth Circuit took a different approach in Texas Tech Physicians
Ass’ns v. DHS , 917 F.3d 837 (5th Ci r. 2019). There the court said in a footnote: Typically, when an agency reaches a decision based on erroneous reasoning, the Chenery doctrine prohibits a reviewing court from upholding that decision for an a lternative re ason. But when an agency gi ves multiple reasons, we may uphold its decision based on any one of those reasons. Salt River Project Agr. Imp. & Power Dist. v. United States , 762 F.2d 1053, 1060 n.8 (D.C. Cir. 1985).36 Id. at 844 n.4 (citation omi tted). In stating that th e court could uphold the decision for any one of the agency’s st ated reasons, the court relied solely on a D.C. Circuit opinion: Salt River Project Agri cultural Improvement & Power District v. United States , 762 F.2d 1053 (D .C. Cir. 1985). See Texas Tech Physicians , 917 F.3d at 844 n.4. Salt River follows the D.C. Circuit’s ordinary approach. Under this approach, the D.C. Circuit has ordinar ily required remand when an agency gives multiple reasons fo r a decision and one or more of the reasons are invalid. See pp. 34–35, above. But th e D.C. Circuit also recognizes that agencies sometimes make clear that they would have reached the same decision even without the invalid reasons. Salt River , 762 F.2d at 1060 n.8.
In Salt River , the D.C. Circuit confronted this situation when an agency had found that a railroad lack ed market dom inance after considering four types of competition: (1) intramodal, (2 ) intermodal, (3) product, and (4) geographic. Id. at 1059. The D.C. Circuit upheld the findings on product a nd geographic competitio n and invalidated the findings on intram odal and intermodal competition. Id. at 1059–65. The court noted that invalidation of some of the agency’s reasons would ordinarily require rema nd because the court ca nnot “presume that the [agency] would have ma de the decision on other, valid grounds.” Id. at 1060 n.8 (quoting Am. Pub. Transit Ass’n v. Lewis , 655 F.2d 1272, 1278 (D.C. Cir. 1981)). Bu t the court decided that it could uphold the agency’s37 ultimate result, reasoning that the ad ministrative findings clearly showed that the agency would have “conclude[d] that [the ra ilroad] lack[ed] market dominance based on its findings on product a nd geographic competition.” Id. 12 We have not yet considered the ne ed to remand when an agency

 gives multiple reasons, some s upported and othe rs unsupported, and

 doesn’t indicate whether the agency would have reached the same result without relying on the unsupported reasons. But both the Supreme Cour t and our court have a ddressed analogous issues. In doing so, both courts have taken an approach resembling the D.C. Circuit’s. For example, we ’ve reversed and remanded when a district court erroneously submits a lega l question to the jury a nd it’s uncertain whether

12 One of the panel members explaine d the importance of clarity in the administrative findings: I join [the majority] opinion, and write separately only to underscore my view that in this case we go to the absolute limits of our ability to uphold an agency’s result, despite error in its subsidiary findings. Normally, where fully one-half the factors relied upon by the agency rest on erroneou s findings and the agency has not stated that its correct findings would, considered alone, have led to the same result, remand is unquestionably required. Only the weakness of the underlying evidence of market dominance in th is case, as ably disc ussed [in the majority opinion], leads me to agree that the agency would indeed have found no market dominan ce had it correctly analyzed the facts. 762 F.3d at 1065 (Wald, J ., concurring).38 the jury relied on an improper view of the law. E.g. , Dillard & Sons Constr., Inc. v. Bur nup & Sims Comtec, Inc. , 51 F.3d 910, 916–17 (10th Cir. 1995). The Supreme Court has done the same when a valid and invalid theory were submitted to the jury and the jury retu rned a general verdict, creating uncertainty on whether the jury relied on the invalid theory. E.g. , Yates v. United States , 354 U.S. 298 , 311–12 (1957), overruled on other grounds by Burks v. United States , 437 U.S. 1 (1978); Williams v. North Carolina , 317 U.S. 287 , 291–304 (1942); Stromberg v. California , 283 U.S. 359, 367–70 (1931). Re quiring reversal in th ese circumstances, the Supreme Court and our court have reasoned that a general verdict cannot stand when the court must speculate on wh ether the factfind er would have reached the same determin ation without an error. Yates , 354 U.S. at 312; Williams , 317 U.S. at 292; Stromberg , 283 U.S. at 368; United States v.
Samora , No. 19-4070, 954 F.3d 1286, slip op. at 13 (10th Cir. Apr. 8, 2020); Dillard & Sons , 51 F.3d at 916; United States v. Dota , 482 F.2d 1005, 1006 (10th Cir. 1973). The same reasoning applie s when we review admi nistrative decisions. Here too we lack the power to “guess at th e theory underlying the agency’s action.” SEC v. Chenery Corp. , 332 U.S. 194, 197 (1947). If we can’t determine whether the agency necessar ily relied on deficient reasons, it would make little sense to uphold the agen cy’s action. In these cases, remand is appropriate “since proceeding on the right path may require or at39 least permit the agency to make qualifications a nd exceptions that the wrong one would not.” Henr y J. Friendly, Chenery Revisited: Reflections on Reversal and Remand of Administrative Orders , 1969 Duke L.J. 199,
223. But a court can someti mes discern from the record whether the agency would have reached the same decision without relying on the unsupported reasons. See, e.g. , Casino Airlines, In c. v. Nat’l Transp. Safety Bd. , 439 F.3d 715, 718 (D.C. Cir. 2006 ) (denying a petition for review because the agency’s decision shows that there is no reasonable dispute that the agency relied on an independent, valid reason rather than the invalid reason); see also pp. 36–37, above (discussing Salt River Project Agric. Improvement & Power Dist. v. United States , 762 F.2d 1053 (D.C. Cir. 1985)). For example, we can uphold administra tive action when an agency gives two independent reason s and only one of them is valid. Am. Fed’n of Gov’t Emps. AFL-CIO, Lo cal 2263 v. Fed. Labor Relations Auth. , 454 F.3d 1101, 1105–07 (10th Cir. 2006); accord Doe v. McAleenan , 929 F.3d 478, 485 (7th Cir. 2019) (“[B]ecause [the agency’s] determination was based on two independ ent and alternative ground s, we would have to find error in both determ inations in order to grant relief to [the petitioner].”). Other administrative determinations are harder to parse. For example,
in Consolidated Edison Co. of New York v. FERC , the D.C. Circuit40 remanded after rejecting one of the ag ency’s justificat ions. 823 F.2d 630, 641 (D.C. Cir. 1987). The court emphasiz ed that the agency’s error had not been “some minor misstatement of law or fact that [could ] be passed over as an unfortunate lapse.” Id. The error had refl ected the agency’s “pervasive frame of mind . . . about a crucial prob lem,” making it difficult to determine whether the agency would have made the same decision without the error. Id. at 641–42. This case presents th e same difficulty. The State Depart ment never said

 whether the State Department’s five reasons were independent or

 what the State Department would have decided if it had not considered the inevitability of in accuracies, surmised a lack of medical consensus, and assumed the infeasibility of a third sex designation. It certainly appears that concern for accuracy was key to the State Department’s decision. Congress has cr iminalized false information in a passport application, 18 U.S.C. § 1542, and the State Department separately requires applicants to trut hfully answer ever y question on the application. 22 C.F.R. § 51.20(b). In the face of a criminal penalty and regulatory requirement, we cannot simply assume that the State Department would have relied on the binary sex po licy even after lear ning that it would create inaccuracies in passports.41 These inaccuracies are inevitable because some people, like Zzyym, are indisputably intersex. But the St ate Department ha s not acknowledged the inherent inaccuracies that arise wh en applying the binary sex policy to these individuals. Without this acknowle dgment or an explan ation for forcing indisputably intersex applic ants to apply as either male or female, the State Department undermined the accuracy of Zzyym’s identify ing information and assumed without any evidence that an intersex designation would be too costly and lack a medical consensus. At the same time, we differ with the district court as to the disposition. The district court conclu ded that the State Department lacked any supportable reasons to rely on the binary sex policy. We disagree. In our view, the State Department reas onably concluded that its policy matched how most jurisdicti ons identified an indivi dual’s sex, facilitating the State Department’s a ssessment of eligibility for passports and other agencies’ use of passport data. We thus

 vacate the district court’s entr y of judgment fo r Zzyym and the court’s issuance of a permanent injunction against enforcement of the binary sex po licy as to Zzyym and

 remand with instructions to va cate the State Department’s decision and reconsider Zzyym’s application for an intersex passport. 13

13 We express no opini on on whether the State Department’s second and third reasons—in themselves—would justify the State Department’sdecision to requir e Zzyym to check either the male or female box on the application. The ultimate evaluatio n would require assessment of a different set of findings. Those findin gs would necessarily be based on the administrative record in existence wh en the State Department reconsiders its decision. See n.4, above.