ORDER AND JUDGMENT*
After Jose Luis Leyva-Ortiz pleaded guilty to violating 8 U.S.C. § 1326(a) and (b) by re-entering the United States after having been deported, the district court sentenced him to a term of forty-six months’ imprisonment. Mr. Leyva-Ortiz now contends that the district court made two procedural errors in determining his sentence: (1) it improperly afforded a presumption of reasonableness to a within-Guidelines sentence; and (2) it failed to adequately explain the sentence that it imposed. He also argues that (3) the sentence was substantively unreasonable.
We are not persuaded that the alleged procedural errors warrant resentencing. The district court did err in applying a *712presumption of reasonableness to a within-Guideline sentence (understandably, given the shifting sands of sentencing jurisprudence over the past few years). However, Mr. Leyva-Ortiz did not object to the presumption in the district court proceedings, and he has failed to establish that he is entitled to resentencing under the plain error doctrine. Moreover, the district court’s explanation of the reasons for the sentence, although brief, was sufficient under our precedent.
Nevertheless, as to substantive reasonableness, we hold that in light of Supreme Court and Tenth Circuit decisions issued after the district court sentenced Mr. Ley-va-Ortiz on August 23, 2007, the district court may not have understood the scope of its discretion to vary from the Guidelines. For that reason, we remand for resentencing.
I. BACKGROUND
On April 3, 2007, United States Border Patrol agents arrested Mr. Leyva-Ortiz near the Columbus, New Mexico Port of Entry. Mr. Leyva-Ortiz admitted that he was a Mexican citizen. Immigration records established that he had been previously deported on March 1, 2007.
Prior to his deportation, Mr. Leyva-Ortiz was convicted in a New Mexico state court of two counts of aggravated assault with a deadly weapon (a fourth-degree felony) and one count of battery with a deadly weapon (a third-degree felony). The state court sentenced him to six years’ incarceration with five years suspended.
In May 2007, Mr. Leyva-Ortiz pleaded guilty to an information alleging that he had reentered the United States after having been convicted of a felony, in violation of 8 U.S.C. § 1326(a) and (b). Under the Guidelines, the district court calculated the offense level at twenty-one, applying a base offense level of eight, a sixteen-point enhancement under USSG § 2L1.2(b)(l)(A)(ii) (because Mr. Leyva-Ortiz had been convicted of “a felony that is ... a crime of violence”), and a three-point reduction for acceptance of responsibility. The court placed Mr. Leyva-Ortiz in criminal history category III, resulting in a Guideline range of 46 to 57 months.
Mr. Leyva-Ortiz then filed a sentencing memorandum seeking a variance from the advisory guideline range. He first argued that the sixteen-level enhancement authorized by § 2L1.2(b)(l)(A)(ii) is unreasonable because it results in an offense level for unlawful reentry crimes that is equal to or greater than the offense level for many violent crimes. Second, he contended that this provision unreasonably “double counts prior convictions by including them in both [a defendant’s] criminal history category and offense level.” Rec. vol. I, doc. 17, at 4 (Sentencing Memorandum, filed Aug. 2, 2007).
Mr. Leyva-Ortiz also argued that the sentencing factors set forth in 18 U.S.C. § 3553 supported a sentence considerably lower than the advisory Guideline range. In his view, the unlawful reentry offense was a nonviolent crime because the “offense conduct itself is akin to trespass.” Id. at 11. Moreover, his 2006 convictions were the result of a single incident. Because he had no other convictions, he maintained, an 18-to-24 month sentence would sufficiently protect the public, deter him from committing other crimes, and promote respect for the law.
At the sentencing hearing, the district court heard arguments regarding the requested downward variance. Mr. Levya-Ortiz’s counsel contended that the case “cries out for a Booker type variance” and asked the court to impose a sentence of 18 months. Rec. vol. Ill, at 2 (Tr. of Sentencing Hr’g on Aug. 23, 2007).
*713The district court rejected Mr. Leyva-Ortiz’s request:
The Court has reviewed the presen-tence report factual findings and has considered the sentencing guideline applications and the factors set forth in 18 United States Code [§ ] 3558(a)(1) through (7).
I’ve thoroughly considered defendant’s sentencing memorandum and find nothing in there to convince me that the presumptively reasonable guideline is anything other than an accurate reflection of the factors I am required to consider.
The offense level is 21. The criminal history category is III. The guideline imprisonment range is 46 to 57 months.
The Court notes the defendant reentered the United States after being removed subsequent to a conviction for an aggravated felony.
Id. at 3-4 (emphasis added). Accordingly, the court imposed a sentence of 46 months’ imprisonment.
II. DISCUSSION
On appeal, Mr. Leyva-Ortiz raises two procedural challenges: (1) that the district court erred in affording a presumption of reasonableness to a within-Guideline sentence; and (2) that it failed to provide an adequate explanation for the 46-month sentence that it imposed. He then argues that the sentence is substantively unreasonable.
In reviewing sentencing challenges, we generally apply a deferential abuse of discretion standard. United States v. Parker, 551 F.3d 1167, 1173 (10th Cir.2008). The review “consists of component parts, affording greater deference to findings of fact (clearly erroneous) than to conclusions of law (erroneous).” United States v. McComb, 519 F.3d 1049, 1054 n. 4 (10th Cir.2007), cert. denied, — U.S.-, 128 S.Ct. 1917, 170 L.Ed.2d 778 (2008). When a defendant fails to preserve an objection to the procedural reasonableness of his sentence, we generally review only for plain error. United States v. Mendoza, 543 F.3d 1186, 1190-91 (10th Cir.2008) (discussing plain error review). In such instances, resentencing is warranted only if (1) there was an error; (2) that was plain; (3) that affected substantial rights; and (4) that “seriously affects the fairness, integrity, or public reputation of judicial proceedings.” Id. at 1190.
A. Because Mr. Leyva-Ortiz did not object to the district court’s application of a presumption of reasonableness to a within-Guideline sentence, he is not entitled to resentencing under the plain error doctrine.
The district court stated at sentencing that it had “thoroughly considered defendant’s sentencing memorandum and [found] nothing in there to convince me that the presumptively reasonable guideline is anything other than an accurate reflection of the factors I am required to consider.” Rec. vol. Ill, at 3-4 (emphasis added). The government concedes, as it must, that this statement was erroneous: a district court may not afford a presumption of reasonableness to a within-Guideline sentence. See United States v. Conlan, 500 F.3d 1167, 1169 (10th Cir.2007) (“Rita [v. United States, 551 U.S. 338, 127 S.Ct. 2456, 168 L.Ed.2d 203 (2007) ] thus makes clear that the presumption of reasonableness applies only at the appellate level.”). However, during the district court proceedings, Mr. Leyva-Ortiz did not object to the application of this presumption. “Ordinarily, ---- [w]hen the party alleging error [in the district court’s sentencing procedure] has not objected in the court below, ... we review only for plain error.” Mendoza, 543 F.3d at 1190.
*714Mr. Leyva-Ortiz does not contend that he has established the elements of plain error. Instead, he maintains that the plain error standard is inapplicable in light of the Supreme Court’s decision in Gall v. United States, 552 U.S. 38, 128 S.Ct. 586, 169 L.Ed.2d 445 (2007). In his view, “[Gall ] set out the standards for review by the appellate courts.... [T]he Supreme Court held that there is a single standard for review of sentences on appeal: [a]buse of discretion.” Aplt’s Reply Br. at 2-3 (citing Gall, 128 S.Ct. at 597). According to Mr. Leyva-Ortiz, Gall holds that a defendant need no longer object to sentencing procedures in order to avoid the deferential plain error standard of review.
We disagree with Mr. Leyva-Ortiz’s reading of Gall. The Supreme Court’s decision holds that “[rjegardless of whether the sentence imposed is inside or outside the Guidelines range, the appellate court must review the sentence under an abuse-of-discretion standard.” Gall, 128 S.Ct. at 597. However, Gall does not address the extent to which various objections to sentencing rulings and procedures must be preserved in order for the defendant to avoid plain error review.
Moreover, contrary to Mr. Leyva-Ortiz’s argument, in post-Gali cases, this circuit has continued to apply the principle that objections to the procedures used in determining a sentence must be made before the district court and that, if no objections are made, our review is only for plain error. See, e.g., United States v. Martinez-Barragan, 545 F.3d 894, 899 (10th Cir.2008) (“As a general rule, when a defendant fails to preserve an objection to the procedural reasonableness of his sentence, we review only for plain error.” citing United States v. Romero, 491 F.3d 1173, 1176-77 (10th Cir.), cert. denied, — U.S.-, 128 S.Ct. 319, 169 L.Ed.2d 225 (2007)); see also Mendoza, 543 F.3d at 1190 (same).
Accordingly, we may review the district court’s application of a presumption of reasonableness of a within-Guideline sentence only for plain error. Under this standard, Mr. Leyva-Ortiz is not entitled to relief. He does not argue that he can establish the required elements, and, on this record, we see no indication that the district court’s statement that it afforded a presumption of reasonableness to a within-Guideline sentence affected either his substantial rights or the fairness, integrity, or public reputation of judicial proceedings. Mendoza, 543 F.3d at 1190-91.
B. The district court did not commit procedural error in explaining the reasons for the 46-month sentence.
Mr. Leyva-Ortiz also argues that the district court committed a second procedural error by failing to provide an adequate explanation for the 46-month sentence. Again, Mr. Levya-Ortiz did not raise this procedural objection in the district court, and we therefore review only for plain error. See United States v. Ruiz-Terrazas, 477 F.3d 1196, 1199 (10th Cir.2007) (reviewing the district court’s alleged failure to provide specific reasons for a sentence for plain error).
Mr. Leyva-Ortiz’s arguments do not persuade. In our view, in explaining the reasons for his sentence, the district court did not commit error at all, much less error that warrants relief under the plain error doctrine. That conclusion follows from the applicable statutes and our precedent.
In particular, 18 U.S.C. § 3553(c)(1) provides that, when the district court imposes a within-Guidelines sentence, it must state “the reason for imposing a sentence at a particular point within the range.” 18 *715U.S.C. § 8553(c)(1). As a general rule, “ § 3553(c)(1) does not impose upon district courts a duty to engage in ... particularized analysis....” United States v. A.B., 529 F.3d 1275, 1289-90 (10th Cir.) (collecting cases), cert. denied, — U.S. -, 129 S.Ct. 440, 172 L.Ed.2d 317 (2008). Instead, the statute requires only a “general statement noting the appropriate guideline range and how it was calculated.” United States v. Cereceres-Zavala, 499 F.3d 1211, 1217 (10th Cir.2007) (quoting Ruiz-Terrazas, 477 F.3d at 1202). We do not require “a ritualistic incantation” or any “magic words” to show us that the district court fulfilled its responsibility to consider the relevant sentencing factors. United States v. Lopez-Flores, 444 F.3d 1218, 1222 (10th Cir.2006) (citation omitted).
In contrast, sentences outside the Guideline range require a more specific explanation. In Ruiz-Terrazas, we observed that, under § 3553(c)(2), the sentencing court must state “the specific reason for the imposition of a sentence [outside the Guideline range] ... which reasons must also be stated with specificity in the written order of judgment and commitment.” Id.
But, even when a non-Guideline sentence is requested, the district court’s explanation of the reasons for its decision need not be extensive. For example, in Ruiz-Terrazas, 477 F.3d at 1198, the defendant argued for a below-Guideline sentence for an unlawful reentry conviction under 8 U.S.C. § 1326(a)(1), (a)(2), and (b)(2) on the grounds that the applicable Guideline provision treated the offense as harshly as more serious crimes. The district court rejected that argument, explaining that it had “reviewed the presentence report[’s] factual findings[,] ... considered the guideline applications^] and the factors set forth in 18 United States Code [§ ] 3553(a)(1) through (7)” and noting that “the defendant reentered the United States subsequent to being convicted of an aggravated felony.” Id. at 1199. The court added that the sentence recommended by the Guidelines was reasonable. However, it did not address the. defendant’s specific arguments for a downward variance.
In our view, that explanation was sufficient. The record in Ruiz-Terrazas established that the district court had entertained the defendant’s downward variance arguments at length, indicated on the record that it had considered the § 3553(a) factors, and “proceeded to explain its reliance on the range suggested by the Guidelines.” 477 F.3d at 1203.
Here, as in Ruiz-Terrazas, the district court heard arguments at the sentencing hearing regarding Mr. Leyva-Ortiz’s request for a downward variance. The court explained that it had read his sentencing memorandum and that it found nothing in it to support a sentence below the Guideline range. The court adopted the presen-tence report’s calculation of Mr. Leyva-Ortiz’s offense level and criminal history and noted that he had reentered the United States after being removed subsequent to a conviction for an aggravated felony. “[N]o more is required by statute or our precedents.” Ruiz-Terrazas, 477 F.3d at 1203.
C. Because the record does not establish that the district court understood its discretion to impose a non-Guidelines sentence, we remand the case for further proceedings.
Finally, Mr. Leyva-Ortiz argues that his 46-month sentence is substantively unreasonable. He repeats the contentions he made to the district court: (1) that USSG § 2L1.2’s sixteen-level enhancement is unreasonable because it establishes an *716offense level for a nonviolent offense that is equal to or greater than the levels for many violent offenses and because it double counts prior convictions by including them in the calculation of defendants’ criminal histories and offense levels; and (2) that the § 3553(a) factors warrant a below-Guidelines sentence.
Mr. Leyva-Ortiz was sentenced on August 23, 2007. At that time, the district court’s authority to impose a non-Guideline sentence based on a policy disagreement with Guidelines was quite limited: we had stated that “a sentencing court may not ignore the Guidelines calculation for the ordinary defendant and instead adopt its own sentencing philosophy.” United States v. Garcia-Lara, 499 F.3d 1133, 1141 (10th Cir.2007) (citing United States v. Hildreth, 485 F.3d 1120, 1129 (10th Cir.2007)), vacated, — U.S. -, 128 S.Ct. 2089, 170 L.Ed.2d 814 (2008). However, subsequent decisions have expanded the district court’s discretion. In light of those decisions, we conclude that the case should be remanded for further proceedings.
In particular, in December 2007, the Supreme Court issued Gall and Kimbrough v. United States, 552 U.S. 85, 128 S.Ct. 558, 169 L.Ed.2d 481 (2007). In Gall, the Court reinstated a variance imposed by a district court, holding that the Eighth Circuit had failed to employ an abuse of discretion standard. In Kimbrough, it held that the district court had discretion to refuse to adopt the Guidelines’ 100:1 crack-to-powder-cocaine sentencing ratio. See 128 S.Ct. at 575.
The Kimbrough Court explained that, in the ordinary case, the Guidelines’ sentencing range will “reflect a rough approximation of sentences that might achieve § 3553(a)’s objectives.” Id. at 574 (quoting Rita v. United States, 551 U.S. 338, 127 S.Ct. 2456, 2465, 168 L.Ed.2d 203 (2007)). On the other hand, “[t]he sentencing judge ... has greater familiarity with ... the individual case and the individual defendant before him than the Commission or the appeals court.” Id. (quoting Rita, 127 S.Ct. at 2469). The sentencing judge is thus “ ‘in a superior position to find facts and judge their import under § [3553](a)’ in each particular case.” Id. (quoting Gall, 128 S.Ct. at 597) (other internal quotation marks omitted). Thus, “[i]n light of these discrete institutional strengths, a district court’s decision to vary from the advisory Guidelines may attract greatest respect when the sentencing judge finds a particular case ‘outside the ‘heartland’ to which the Commission intends individual Guidelines to apply.’” Id. at 574-75 (quoting Rita, 127 S.Ct. at 2465). Nevertheless, “closer [appellate] review may be in order when the sentencing judge varies from the Guidelines based solely on the judge’s view that the Guidelines range fails properly to reflect § 3553(a) considerations even in a mine-run case.” Id. (internal quotation marks omitted).
In considering the crack cocaine Guidelines, the Kimbrough Court further observed that there was “no occasion for elaborative discussion of this matter because those Guidelines do not exemplify the Commission’s exercise of its characteristic institutional role.” Id. Instead, in formulating those provisions, the Commission looked to the mandatory minimum sentences set forth in a 1986 statute and “‘did not take account of empirical data and national experience.’” Id. (quoting United States v. Pruitt, 502 F.3d 1154, 1171 (10th Cir.2007) (McConnell, J., concurring)). Additionally, the Sentencing Commission itself had unsuccessfully recommended revising the crack cocaine provisions of the Guidelines because they did *717not reflect the purposes of sentencing set forth in § 3553(a).
Examining Gall and Kimbrough, we have concluded that those cases cannot be reconciled with prior circuit cases regarding non-Guideline sentences. See United States v. Smart, 518 F.3d 800, 806-08 (10th Cir.2008) (discussing the abrogation of Garcia-Lara, 499 F.3d at 1140-41). Now, “[w]e may not conclude that simply by diverging from the Guidelines, a district court has disregarded the policy considerations which led the Commission to create a particular Guideline.” Id. at 809 (emphasis added). The district courts are authorized to “contextually evaluate each § 3553(a) factor, including those factors that the relevant guideline(s) already purport to take into account, even if the facts of the case are less than extraordinary.” Id. at 808. A district court does not abuse its discretion merely by balancing the Guidelines with the § 3553(a) factors, striking a different balance than the Guidelines and imposing a variance. Id. at 809. Nevertheless, following the Supreme Court’s observation in Kimbrough, we have recognized that “in a mine-run case” a “closer review” may be warranted when the district court varies from the Guidelines solely because the Guidelines range fails properly to reflect § 3553(a) considerations. Id. at 808 n. 5 (quoting Kim-brough, 128 S.Ct. at 575).
These developments have led this court, as well as others, to remand cases for reconsideration of a defendant’s request for a downward variance when (a) the defendant was sentenced before the Supreme Court issued Gall and Kimbrough; (b) a direct appeal of the sentence had not been finally resolved when those opinions were issued; and (c) the record indicated that the district court may not have fully comprehended its discretion to impose a non-Guidelines sentence, See, e.g., United States v. Trotter, 518 F.3d 773, 774 (10th Cir.2008) (remanding to the district court “to clarify why it rejected [the defendant’s] request for a variance based on the crack/powder disparity” and stating that, if the court “rejected this request based on a belief that it did not have discretion to specifically consider whether the disparity resulted in a disproportionately harsh sentence, [it] is to conduct resentencing in light of Kimbrough”); see also United States v. Vanvliet, 542 F.3d 259, 271 (1st Cir.2008) (observing that “the government correctly points out that [the defendant’s] sentence must be vacated in light of Kim-brough ” when the district court expressed disagreement with “the Guidelines policy to enhance a sentence for his use of a computer” but when the district court further stated that a disagreement with a Guidelines policy would not support a below-Guidelines sentence and adding that “[Kimbrough ] was not available to the district court when it made its sentencing decision”); United States v. Padilla, 520 F.3d 766, 774 (7th Cir.2008) (stating that “[b]eeause we cannot ascertain with any exacting degree of certainty whether the sentencing judge would have imposed the same term of incarceration in the wake of Kimbrough, and because we find that the issue was adequately preserved, a remand is appropriate”).
Here, when it sentenced Mr. Leyva-Ortiz, the district court did not have the benefit of Gall, Kimbrough, or this circuit’s decision in Smart, which read those Supreme Court decisions to expand the discretion to impose a non-Guidelines sentence “even if the facts are less than extraordinary.” Smart, 518 F.3d at 808. Moreover, as we have noted, the district court appears to have improperly afforded a presumption of reasonableness to a within-Guidelines sentence. Thus, when Mr. Leyva-Ortiz argued in his sentencing memorandum that USSG § 2L1.2’s 16-lev-*718el enhancement was unreasonable, the district court may not have fully understood its discretion to grant a downward variance.
III. CONCLUSION
Accordingly, we conclude that a remand is warranted so that the district court may reconsider Mr. Leyva-Ortiz’s request for a downward variance in light of those recent decisions. On remand the district court should exercise its discretion to balance the § 3553(a) factors and the Guidelines. See Smart, 518 F.3d at 807-09.
Following the decisions of our sister circuits, “[w]e signal no criticism of the able and conscientious district judge. Nor do we express any view as to what sentence [Mr. Leyva-Ortiz] should receive on remand or whether it should fall within or outside his Guidelines range.” United States v. Jones, 531 F.3d 163, 182 (2d Cir.2008); see United States v. Boardman, 528 F.3d 86, 88 (1st Cir.2008) (“Nothing in our decision is intended to suggest that a lesser sentence be imposed.... ”). On remand, the district court should choose an appropriate sentence and explain the reasons for it.
We therefore REMAND this case to the district court with instructions to resen-tence Mr. Leyva-Ortiz after considering his request for a below Guideline sentence in a manner consistent with this order and judgment.