# Creating a More Equitable Introductory Physics Classroom Through
Invitational Phrasing in Question Solicitation

David Frykenberg  Brokk Toggerson<EMAIL_ADDRESS>Adena Calden
Chris Ertl  University of Massachusetts Amherst, Amherst, Massachusetts 01002,
USA

###### Abstract

Asking questions during class time is one form of participation not commonly
employed by members of underrepresented groups in large enrollment college
classrooms, even though the form of participation is highly conducive to
student learning. To encourage students to ask questions, many instructors
initiate open question periods in their lectures with verbal solicitations
(i.e., “Questions?”). Although several university centers for teaching and
learning, such as at UC Berkeley, and instructor reflections suggest that the
scripts of question solicitations impact the frequency of questions returned
by students, no literature exists to support this claim. This quasi-
experimental scholarship of teaching and learning (SoTL) study conducted with
the Students-as-Partners model, observes the effect of a new solicitation
script integrated into an introductory physics lectures to improve question
participation from students. While the new solicitation script did not change
the total number of questions asked by students in comparison to previous
scripts, the number of questions asked by people who likely have gender
identities traditionally underrepresented in physics (i.e. all but cis-men)
increased significantly.

##  I  Introduction

“Reflection is an integral part of [the Scholarship of Teaching and Learning
(SoTL)] because it is an integral part of learning itself” [1]. Instructors
who reflect on their teaching often note and lament the lack of questions from
students. As student questions are an important form of classroom
participation that largely benefits student learning, interventions made by
instructors to increase student questioning are especially important in
improving classroom equity, particularly in light of the noticeable
discrepancy in the fraction of in-class questions asked by students from
underrepresented groups. Thus, instructors clearly have a pivotal role in
promoting equity in their classrooms through their influence on their
students’ willingness to ask questions.

Conventional wisdom suggests that an instructor can promote student
questioning via the specific language used in question solicitation. For
example, the Center for Teaching and Learning at UC Berkeley recommends using
“What questions do you have?” as opposed to a more general “Questions?” [2].
Little, if any, SoTL research, however, exists to support such
recommendations, and challenging such “conventional wisdom” is another key
aspect of SoTL [3].

This study aims to explore these issues: to determine if a change in how an
instructor solicits student questions impacts participation with the intent of
identifying ways to promote equity in learning. Following best SoTL practices,
this study uses the Students-as-Partners model to provide diverse perspectives
on the context of the course [4]. Prior to leading this study, the lead author
was a student in the course and then an undergraduate teaching assistant.

###  I.1  Student Participation and Questions in the College Classroom

Higher education currently has a growing preference for active learning,
participation-rich classrooms, as opposed to traditional lecture formats where
students passively take in information [5] [6] [7]. The literature on active
learning shares a consensus that in-class participation is beneficial to
student learning [8] [9] [10] [7]. Students who participate in class are more
academically motivated and exhibit higher levels of academic achievement in
comparison to students who do not participate [8] [6] [9] [10] [11] [7]. The
common forms of in-class participation include: classroom discussion, small
group involvement, as well as the willingness to ask and answer questions vis-
à-vis the instructor [9] [12].

Among these forms, the simple practice of asking questions is especially
important because of the wide range of learning benefits it provides students
[13] [14] [15] [16] [17]. Students who pose questions to their instructor
improve their problem-solving abilities and gain a more holistic understanding
of material as it relates to other subjects [13]. Those same inquisitive
students who receive responses from their instructors become more motivated to
learn in their courses [14] [15] [18]. Furthermore, students who generate
questions improve their study habits and show signs of reduced anxiety during
examinations [13] [16]. Peers of students who ask questions also benefit
because they often harbor the same questions, gain new perspectives from
questions they did not previously consider, and become more engaged in a class
from the variety of questions added to the lesson-structure [17].

Unfortunately, it is likely that most students do not reap the benefits of
asking questions in class or from general classroom participation. Colleges
and universities commonly report a widespread lack of class-time student
participation, specifically in the form of student questioning [15] [16] [19]
[20] [21]. Looking at the total number of questions asked in a lesson,
teachers clearly ask more questions than students [14] [16].

###  I.2  Improving Equitable Learning Through Classroom Participation

In addition to classroom participation, equity in student learning is another
focus of modern education. Equitable learning is defined by providing equal
learning opportunities to students, regardless of gender or socioeconomic
background [22]. The motivation for integrating equitable learning into modern
education is founded on the assertion that school classrooms are culturally
biased environments which manifest as barriers relating to school
organization, availability of resources, and classroom attitudes [23] [24].

College classroom participation is one area where such barriers could
potentially cause inequitable learning outcomes. Aside from the issue of its
general lack in higher education, low classroom engagement is particularly
pronounced in traditionally underrepresented social groups [25] [17] [11] [7].
Some reasons for this lack of engagement originate from the logistical
structure of the classroom and from its method of instruction, including class
size and the instructor’s communication style [26] [8] [9] [21] [11]. Other
causes are derived from the student population of the class, such as student
preparation, language barriers, and student emotions relating to participation
[9] [21] [7].

One major factor contributing to the infrequency of student participation in
college classrooms is stereotype threat. Underrepresented groups participate
less than other students because they fear judgement and discrimination from
their peers [25] [7]. Furthermore, when a student belongs to a traditionally
underrepresented group, they may also avoid participating in class for fear of
misrepresenting their culture [25] [7]. Coinciding with feelings of cultural
alienation, underrepresented groups often do not engage in class because of
their self-perception of intellectual and academic inadequacy [25].

The goal of making classrooms more equitable and welcoming of student
participation have yielded various teaching interventions. An instructor can
generally raise in-class participation by setting standards for participation
at the beginning of the course, acknowledging times for participation during a
lesson, and giving students feedback when they participate [12] [11].
Additionally, instructors improve participation, especially with regards to
underrepresented groups, by presenting themselves informally and by expressing
openness to student opinion [18] [27] [21]. The existing research on how to
promote student questioning also shares the conclusion that student questions
are primarily impacted by the instructor’s personable character and
communication style [18] [21]. One of the ways instructors communicate to
their class and encourage questions in their students is by simply asking them
if they have any questions [28]. However, as stated in the introduction, there
is little SoTL research as to the efficacy of particular interventions such as
the switch from “Questions?” to “What questions do you have?” which are
commonly advocated by such institutions such as the UC Berkeley Center for
Teaching and Learning [2].

###  I.3  Equity in the Physics Classroom

Another of Felten’s Principles of Good Practice in SoTL is the grounding of
the work within a particular context [4]. In this case, the context is a large
( 300 student) introductory physics course which is the second of a two-
semester sequence for life science majors at a public R1 university in New
England.

If our goal is to promote equity in physics classrooms, then we must
understand equity issues in physics. Within physics generally, students who do
not identify as cis-men are traditionally underrepresented, and a great deal
of literature explores the negative correlations between this minoritized
status and performance [29]. However, such overarching statistics may not be
representative of the experiences of students who do not identify as cis-men
in an introductory physics for life sciences course where the population
generally self-identifies with she/her pronouns. However, the reflections of
the authors as a former student/undergraduate TA and as the instructor of the
course seem to indicate a disparity in questions asked between these two sub-
populations. This perceived discrepancy is in line with the work of Eddy et
al. who has also shown that the stereotype threat of women in science can
extend to disciplines where the majority of students are not cis-men such as
in biology [30].

##  II  Methodology

The aim of the research is to gather data that would reveal whether there are
common features of an instructor’s language in question solicitation that
impact student participation. Two research questions guided this study:

  1. 1.

Are there common features of question solicitation which lead to an increase
in student participation?

  2. 2.

Is it possible to identify solicitation characteristics which promote a more
equitable classroom through increasing the frequency of questions from
traditionally underrepresented groups, in our case students who do not
identify as cis-men?

Through analysis of recorded lectures, students’ questions and presumed
genders were tracked for every verbal solicitation initiated by the instructor
of a physics classroom. Prior to the start of the study, the instructor of the
course, following the advice of institutions such as CTL, UC Berkeley, had
already chosen a solicitation script following the form, “what questions do
you have?” for spring 2020. In contrast, during the spring 2019 semester, the
instructor used whatever solicitation came to mind. However, the instructor
consistently used variants of “Questions on this?” or “Any questions?” during
this prior semester.

Data from this study uses the lecture recordings of a physics course that took
place in the spring semesters of 2019 and 2020 at a large R1 university in New
England. Specifically, the first two units of the course in each semester were
used for observation as the standard teaching structure of the course changed
in the latter half of 2020 due to the outbreak of SARS-CoV-2 which caused
students to switch to remote learning. The class sizes from both semesters
were approximately the same, with 303 students initially enrolled in 2019 and
301 students initially enrolled in 2020. Demographically disaggregated by
gender, the 2019 class section had 64.4% self-identify as women and 35.6%
self-identify as men. Meanwhile, the 2020 class section had 67.1% self-
identify as women and 32.9% self-identify as men Figure 1. In each case, there
was also a handful of students with other identities who do not statistically
impact the outcomes of this study.

Figure 1:  Distribution of student gender identities in 2019 and 2020. note:
The percentage ratios, women to men, in 2019 and 2020 were 64.4%:35.6% and
67.1%:32.9% respectively. These data were taken from the beginning of each
course before any students dropped out of the class. In each case, there was
also a handful of students with other identities who do not statistically
impact the outcomes of this study.

Echo360, an automated lecture-capture system integrated into many STEM
classrooms at the university, provided the recordings for data collection. For
this course, Echo360 serves as an aid in making scientific demonstrations
visible to the entire class and to enable students to review lectures
including to those students who cannot attend a lecture because of extenuating
circumstances. The class recordings provide visuals of lecture presentation
slides as well as a video capture of the entire lecture hall from the back of
the classroom. The audio comes from the instructor’s microphone.

Access to the Echo360 recordings was provided by the instructor of the course:
a 38-year-old, white, cis-male who was born and raised in the US. Recordings
were organized by lecture, course unit, and the year during which the Spring
semester took place. For every recording, audio with corresponding lecture
slides were observed for question solicitations made by the instructor.

The recording audio was the only source of question solicitation
identification. The slides, however, provided context. Question solicitations
were identified by two conditions: the instructor addressed the classroom’s
student-body; and the instructor explicitly inquired into whether the students
had any questions. A feature present in all solicitation scripts is the word,
“questions,” a commonality which aided in the identification process. Only
solicitations from the primary instructor, as opposed to one of the TAs
circling the room, were considered and the time within the 50-minute lecture
was also recorded.

In addition, solicitations were also categorized as to whether they were
initiated following the explanation of material or in response to a previous
question posed by a student. Solicitations classified as “topic” (for “topic-
initiated question solicitations”) were made after the instructor finished
explaining some content. Alternatively, “sequence” solicitations (for
“question solicitations initiated as part of a sequence of student questions”)
come in response to a student-asked question during the class. A sequence was
marked complete when no more questions were posed by students and the
instructor moved on to other lecture content. A transition often also
partially identified by the instructor, who might announce something along the
lines of, ‘if there are no more questions, we will move on to…’.

We classified any students who asked questions in response to the solicitation
as cis-male or not based purely on listening to the recording audio (the
students are not visible in the recording). Given that the significant
majority of students who are not cisgender men identify as women, we use that
term in our results though we acknowledge that there are trans-men and non-
binary individuals in this group. The primary distinguishing characteristic is
fundamental frequency based on linguists’ known practice of identifying an
individual’s gender by his or her voice and the distinguishability of
fundamental frequency amongst cis and trans individuals [31] [32]. Prior to
observation of the 2019 and 2020 data, researchers of the study conducted an
inter-rater reliability test on data from Spring 2018 and found perfect
agreement in their assessments.

##  III  Results

Students asked an equal forty-nine total questions in each semester. In the
context of the first research question, this information implies that the 2020
solicitation script may not contain any new features over 2019 which
significantly differ in their impact on the total number of questions asked by
students. Alternatively, there may be new features present in the 2020
solicitation scripts whose effects are superseded by other factors not
accounted for in the available data, such as the instructor’s time management
of the lesson.

In the spring 2019 semester, 38.8% of the questions asked were from women
(strictly, students not identified as cisgendered men). In spring 2020 by
contrast, 67.3% of the questions asked were from women. These percentages were
calculated by dividing the number of questions asked by women in each semester
by the respective total number of questions asked in that semester (Table 1).

Table 1:  Solicitations Made, Total Number of Questions Asked, Questions Asked by Women, and the Percentage of Questions Asked by Women for Each Semester. Note: The percentages were calculated by dividing the number of questions asked by women in each semester by the respective total number of questions asked in that semester. Semester | N Solicitations | N Questions | N Questions from Women | Average %F
---|---|---|---|---
2019 | 46 | 49 | 19 | 38.8%
2020 | 43 | 49 | 33 | 67.3%
Difference | 3 | 0 | 14 | 28.5%

A Pearson’s $\chi^{2}$-Test was used to measure the difference between the
percentages in each semester. The binomial nature of the data and its
independent collection in two separate semesters prompted the use of this test
for statistical analysis. The null hypothesis specifies that the percentage of
questions asked by women in the class section given the new solicitation
script (spring 2020) does not differ significantly from the percentage of
questions asked by women in the class section not given the new solicitation
script (spring 2019). Conversely, the alternative hypothesis specifies that
the percentage of questions asked by women in the class section given the new
solicitation script does differ significantly from the percentage of questions
asked by women in the class section not given the new solicitation script. As
the number of questions asked in each semester was significantly greater than
5, the continuous $\chi^{2}$ distribution is a reasonable approximation for
the discrete data in this study (Cochran’s Rule).

The full results of the $\chi^{2}$ test are in Table 2. An $\alpha=0.01$ was
chosen to assess the probability of falsely rejecting the null hypothesis from
the $\chi^{2}$ test result. The data yield a $\chi^{2}=8.03$. As this
$\chi^{2}$ test value exceeds 6.63, the $\chi^{2}$ value corresponding to
$p=0.01$ with 1 degree of freedom, the null hypothesis is rejected. Instead,
the alternative hypothesis, stating that the percentage of questions asked by
women in 2020 does differ significantly from the percentage of questions asked
by women in 2019, can be tentatively accepted. It is possible that the
solicitations from 2020 are distinct from those of 2019 and contain a feature,
or multiple, that is responsible for the observed increase in questions asked
by women.

Table 2:  $\chi^{2}$ Contingency Table and Test Result for Questions Asked by Men and Women in Each Semester. Note: For each cell, the numbers in parentheses indicate the expected values and the numbers in brackets indicate the test statistics. Variable | F | M | Marginal Row Totals
---|---|---|---
2019 | 19 (26) [1.88] | 30 (23) [2.13] | 49
2020 | 33 (26) [1.88] | 16 (23) [2.13] | 49
Marginal Column Totals | 52 | 46 | 98 (Grand Total)
$\chi^{2}$ Test Result | $\chi^{2}(\mathrm{dof}=1,\;N=98)=8.03,\;\;p=0.0046$

##  IV  Discussion

To determine what feature, or features, distinguished 2020 solicitation
scripts from those of 2019, researchers of this study observed the data pools
and found internal consistency amongst script formats within each of the
semesters. All the solicitations from the 2020 data reflected the chosen
style, “What…questions do [you all] have…?”. Likewise, with one exception, the
2019 solicitations followed two basic formats, “Questions on…this?”, and
“Any…questions?” in order of frequency. The 2020 format contains an implicit
assumption: that students already possess questions at the time of the
solicitation. Conversely, the formats for 2019 simply probe the classroom to
check that no questions exist on a topic before proceeding with the lecture.
If students perceive such a perfunctory intent, it could be perceived as
questions not being wanted. If these presumed interpretations match students’
actual experiences that would possibly help explain why female students in
2019 were less likely to ask questions than women in 2020.

Although this study did not initially have this experimental design, the
consistencies found in the solicitation scripts and within demographic data
from 2019 and 2020 allow the results of the study to be more confidently
interpreted as effects of solicitation formatting. Specifically, the
consistencies provide support for the interpretation that women in 2020 asked
more questions than women in 2019 because of the formatting of the 2020
solicitation script. Thus, although at its inception this study was
observational, the consistencies in the data mentioned have allow this study
to be redefined as quasi-experimental.

Such a shift in study design suggests some adjustments which should be
addressed in future work. Although the consistency amongst the solicitations
in 2019 allowed for comparison between 2019 and 2020, the instructor did not
consciously choose a specific script in spring 2019 before the study began.
Additionally, the while the instructor did choose the 2020 “What Questions do
you have?” solicitation format to have the supposed implicit assumption that
students already had questions, this choice was not backed by previous studies
providing evidence on this solicitation format’s effectiveness on student
participation. Moreover, there is no way to measure this supposed implicit
assumption via an assessment tool or other means, because no such tool
currently exists. Such a tool would facilitate a more thorough consideration
of the particular features of various solicitations which may, or may not,
promote equitable student questioning.

Even if such a tool to measure the implicit assumptions of different
solicitations existed, determining the exact effect a solicitation might have
on promoting questions from students would be challenging. Many factors
contribute to the degree to which students are encouraged to ask questions.
For example, students may feel more inclined to ask questions if someone else
has already asked a question on the same topic. While student questions were
categorized as “topic” or “sequence,” the results did not incorporate this
categorization. Including this distinction may provide additional insights as
the two categories may have distinct mechanisms of inspiring questions from
students.

The technology recording the lectures’ audio also limited a deeper, more
thorough analysis of the data. As a microphone on the instructor’s person was
the sole source of the audio, students’ voices were audible, but the words of
their responses were indiscernible. As such, distinguishing between student
questions apart from other student vocalizations directly was impossible; only
instructor comments allowed for an indirect method of differentiation.
Moreover, the audio quality made identifying a single student who asked
multiple questions impossible. Microphones situated throughout the room,
perhaps in combination with video, could alleviate these concerns.

##  V  Conclusions

This Students-as-Partners SoTL study finds that using a question solicitation
script “What questions do you have?” in a second-semester introductory physics
for life science students can produce a higher fraction of questions arising
from students who are not cis-men, a group traditionally underrepresented in
physics. We speculate that that the primary feature which results in this
higher participation is an implicit assumption that students possess questions
at the time of a solicitation. However, more research is required to confirm
which features of specifically influence student questioning. More classroom
data from various courses and instructors with various identities, would also
strengthen the study, as would more thorough observation of lectures (via
video or live observation) to better identify which students were asking
questions. Ultimately, integrating measures of psychological features of
classrooms and students may aid in developing an assessment tool for
invitational properties of question solicitation.

Aside from the central finding that women’s questions increased in response to
the “What questions do you have?” question solicitation script, this study
could not prove that this script had any new features over prior scripts
affecting the total number of questions asked by students. Considering the
results of this study, question solicitation claims made by centers for
teaching and learning at UC Berkeley are partially supported, albeit with
little specification for which features of question solicitation affect
student participation. The results of this study hold promise for educational
application and development of equitable learning environments.

##  VI Acknowledgments

The authors wish to acknowledge the support of the University of Massachusetts
Amherst for their financial support of this work through various internal
grants with particular thanks to the Center for Teaching and Learning. We
particularly thank Colleen Kuusinen for her help in developing this Students
as Partners Scholarship of Teaching and Learning Survey.

## References

  * Cook-Sather  _et al._ [2019] A. Cook-Sather, S. Abbot, and P. Felten, Teaching and Learning Inquiry 7, 14 (2019).
  * [2] Asking and Answering Questions | Center for Teaching & Learning.
  * Norton [2009] L. Norton,  _Action Research in Teaching and Learning: A Practical Guide to Conducting Pedagogical Research in Universities_ (Routledge, 2009).
  * Felten [2013] P. Felten, Teaching and Learning Inquiry 1, Article 1 (2013).
  * Fayombo [2012] G. Fayombo, Mediterranean Journal of Social Sciences 3, 16 (2012).
  * Obenland  _et al._ [2013] C. A. Obenland, A. H. Munson, and J. S. Hutchinson, Chem 14, 73 (2013).
  * White [2011] J. W. White, Journal of Language, Identity, and Education 10, 250 (2011).
  * Kumaraswamy [2019] S. Kumaraswamy, International Journal of Instruction 12, 369 (2019).
  * Rocca [2010] K. A. Rocca, Communication Education 59, 185 (2010).
  * Voelkl [1995] K. E. Voelkl, Journal of Experimental Education 63, 127 (1995).
  * Wenzel [2003] T. J. Wenzel, Analytical Chemistry 75, 311 A (2003).
  * Vandrick [2000] S. Vandrick, (2000).
  * Aflalo [2021] E. Aflalo, Active Learning in Higher Education 22, 63 (2021).
  * Almeida [2012] P. A. Almeida, Procedia Social and Behavioral Sciences 31, 1 (2012).
  * Chin and Osborne [2008] C. Chin and J. Osborne, Studies in Science Education 44, 1 (2008).
  * Harper  _et al._ [2003] K. A. Harper, E. Etkina, and Y. Lin, Journal of Research in Science Teaching 40, 776 (2003).
  * Nadile [2021] E. M. e. a. Nadile, PLOS ONE 16, e0243731 (2021).
  * Gasiewski  _et al._ [2012] J. A. Gasiewski, M. K. Eagan, G. A. Garcia, S. Hurtado, and M. J. Chang, Research in Higher Education 53, 229 (2012).
  * O’Connor [2013] K. J. O’Connor, Education 133, 340 (2013).
  * Ratto  _et al._ [2003] M. Ratto, R. B. Shapiro, T. M. Truong, and W. G. Griswold, The activeclass project: Experiments in encouraging classroom participation, in  _Designing for Change in Networked Learning Environments_ (Springer Netherlands, 2003) p. 477–486.
  * Weaver and Qi [2005] R. R. Weaver and J. Qi, The Journal of Higher Education 76, 570 (2005).
  * de los Santos  _et al._ [2020] J. de los Santos, M.-G. P., and M.-M. A.-J., International Journal of Environmental Research and Public Health 17, 3526 (2020).
  * Clark [2014] I. Clark, Improving Schools 17, 116 (2014).
  * Sanchez  _et al._ [2019] P. A. Sanchez, R. d. Haro-Rodriguez, and R. M. Martinez, Journal of New Approaches in Educational Research (NAER Journal) 8, 18 (2019).
  * Eliason and Turalba [2019] M. J. Eliason and R. Turalba, The Review of Higher Education 42, 1257 (2019).
  * Bahmanbijar  _et al._ [2019] B. Bahmanbijar, M. Nazarieh, N. Toufan, M. R. Dehghani, and A. Beigzadeh, Future of Medical Education Journal 9, 10 (2019).
  * Roehling  _et al._ [2010] P. V. Roehling, T. L. V. Kooi, S. Dykema, B. Quisenberry, and C. Vandlen, College Teaching 59, 1 (2010).
  * Micari and Calkins [2021] M. Micari and S. Calkins, Active Learning in Higher Education 22, 143 (2021).
  * Kost  _et al._ [2009] L. E. Kost, S. J. Pollock, and N. D. Finkelstein, Physical Review Special Topics - Physics Education Research 5, 010101 (2009).
  * Eddy  _et al._ [2014] S. L. Eddy, S. E. Brownell, and M. P. Wenderoth, CBE-Life Sciences Education 13, 478 (2014).
  * Levitan  _et al._ [2016] S. I. Levitan, T. Mishra, and S. Bangalore, Speech Prosody 2016, 84 (2016).
  * Hardy  _et al._ [2020] T. L. D. Hardy, J. M. Rieger, K. Wells, and C. A. Boliek, Journal of Voice 34, 300.e11 (2020).


# Bhattacharyya parameter of monomials codes for the Binary Erasure Channel:
from pointwise to average reliability

Vlad-Florin Drăgoi 1,2 and Gabriela Cristescu 1

(1Faculty of Exact Sciences, Aurel Vlaicu University of Arad, Romania;
<EMAIL_ADDRESS>
2LITIS, University of Rouen Normandie, France. )

###### Abstract

Monomial codes were recently equipped with partial order relations, fact that
allowed researchers to discover structural properties and efficient algorithm
for constructing polar codes. Here, we refine the existing order relations in
the particular case of Binary Erasure Channel. The new order relation takes us
closer to the ultimate order relation induced by the pointwise evaluation of
the Bhattacharyya parameter of the synthetic channels. The best we can hope
for is still a partial order relation. To overcome this issue we appeal to
related technique from network theory. Reliability network theory was recently
used in the context of polar coding and more generally in connection with
decreasing monomial codes. In this article, we investigate how the concept of
average reliability is applied for polar codes designed for the binary erasure
channel. Instead of minimizing the error probability of the synthetic
channels, for a particular value of the erasure parameter $p$, our codes
minimize the average error probability of the synthetic channels. By means of
basic network theory results we determine a closed formula for the average
reliability of a particular synthetic channel, that recently gain the
attention of researchers.

##  1 Introduction

One of the most striking development in coding theory in the last two decades
is probably the theory around polar codes. In his seminal article [1], Arikan
demonstrated, for the first time, that one could achieve the capacity of
Binary Discrete Memoryless Channels (BDMC) using both efficient encoding as
well as efficient decoding algorithms. The so called polar codes are now
present in the fifth generation (5G) technology [2]. Indeed, polar code was
elected as the standard coding technique for the control channel in support of
the enhanced Mobile BroadBand service, one of the major parts in the 5G
wireless network technology. Getting back to the three principal directions on
which coding theory evolved, _polar coding_ seemed to be unrelated to the
classical _algebraic coding_. Typically, the construction of polar codes does
not come from any particular structure in the code but rather from the process
of channel polarization. However, polar codes are closely related to Reed-
Muller codes, as pointed out even by Arikan [1]. Hence, polar and Reed-Muller
code share a common algebraic description [3, 4]. More precisely, they are
sub-classes of a bigger family of algebraic codes called _decreasing monomial
codes_ (DMC). The structure underlying DMCs and its algebraic formalism were
applied in conjunction with other fields, e.g., in the context of quantum
error correcting codes [5, 6, 7], post-quantum cryptography [8, 9, 10],
network reliability [11, 12, 13].

Several challenges regarding polar coding, among which efficient construction
of polar codes given a specific BDMC, were proposed. Arikan’s initial
technique [1] was improved by several authors [14, 15, 16, 17, 18, 19, 20, 21,
22]. Let $W$ denote a BDMC, $m$ a fixed integer and $\boldsymbol{u}$ a binary
vector of length $m.$ The main idea in the construction of polar codes is to
estimate the reliability of the synthetic channels
$\\{W^{\boldsymbol{u}}\;|\;\boldsymbol{u}\in\\{0,1\\}^{m}\\}$. For that one
might use the Bhattacharyya parameter
${\mathcal{B}\left(W^{\boldsymbol{u}}\right)}(p)$, where $p$ denotes the error
probability of the channel $W$. The message bits of a polar code of length
$2^{m}$ and dimension $k$ are allocated to the $k$ sub-channels
$W^{\boldsymbol{u}}$ having the smallest
${\mathcal{B}\left(W^{\boldsymbol{u}}\right)}$. Hence, one might classify the
set of $W^{\boldsymbol{u}}$ into ”good” (reliable) or ”bad” (non-reliable).
For a fixed value of $p$ the values
${\mathcal{B}\left(W^{\boldsymbol{u}}\right)}(p)$ are totally ordered. In
other words, when the parameter $p$ is fixed any distinct pair of channels
$W^{\boldsymbol{u}},W^{\boldsymbol{v}}$ satisfy either
${\mathcal{B}\left(W^{\boldsymbol{u}}\right)}(p)\leq{\mathcal{B}\left(W^{\boldsymbol{v}}\right)}(p)$
or
${\mathcal{B}\left(W^{\boldsymbol{v}}\right)}(p)\leq{\mathcal{B}\left(W^{\boldsymbol{u}}\right)}(p).$
In this case, we say that a channel $W^{\boldsymbol{u}}$ is point-wise more
reliable than a channel $W^{\boldsymbol{v}}.$ However, when considering the
whole interval $p\in[0,1]$, ranking the synthetic channels becomes
complicated. In this case we say that $W^{\boldsymbol{u}}$ is globally more
reliable than $W^{\boldsymbol{v}}$, and write
$\boldsymbol{u}\leq\boldsymbol{v}$, if and only if $\forall
p\in[0,1]\;,\;{\mathcal{B}\left(W^{\boldsymbol{u}}\right)}(p)\leq{\mathcal{B}\left(W^{\boldsymbol{v}}\right)}(p).$

One of the most efficient techniques that orders the set of synthetic channels
(with respect to the concept of globally more reliable), provides sub-linear
complexity construction [14]. It exploits the existence of a partial order
(denoted by $\preceq$) on the set of synthetic channels [4]. This partial
order is compatible with the notion of globally more reliable, i.e.,
$\boldsymbol{u}\preceq\boldsymbol{v}\Rightarrow\boldsymbol{u}\leq\boldsymbol{v}.$
Relation $\preceq$ was also applied in other contexts. In [4] the authors
proved fundamental properties of polar codes by means of an algebraic
formalism. The order $\preceq$ played a crucial role in proving that code-
based cryptosystems employing polar codes are insecure [8, 9]. Even though
$\preceq$ provided a contribution to understanding polar codes, i.e., their
structure and construction, simulations show that $\preceq$ is far from
ordering ${\mathcal{B}\left(W^{\boldsymbol{u}}\right)}$ optimally. Hence, in a
recent article $\preceq$ was refined [23].

In the analysis of the performance of several families of codes, among which
polar, Reed-Muller, cyclic and BCH codes, the communication channel that
received a lot of attention is the Binary Erasure Channel ($\mathrm{BEC}$).
When polar codes are designed for $\mathrm{BEC}(p)$ (in this particular case
$p$ denotes the erasure probability) all the synthetic channels
$\\{W^{\boldsymbol{u}}\;|\;\boldsymbol{u}\in\\{0,1\\}^{m}\\}$ are also
$\mathrm{BEC}$. In this case, the erasure probability of $W^{\boldsymbol{u}}$
is equal to the Bhattacharyya parameter of $W^{\boldsymbol{u}}.$ Here, we
analyze this particular channel. Our choice is motivated by several results
and methods. First of all the simplicity of this channel makes the theoretical
proofs significantly simpler and easier. Also, many of the properties that
hold for the $\mathrm{BEC}$ turn out to be valid for more general channel
models. For example, the proof of Reed-Muller codes achieving the capacity of
a communication channel started with the $\mathrm{BEC}$ [25, 24]. Codes that
admit a doubly-transitive automorphism group or having large orbits under the
action of their permutation group achieve the capacity of the $\mathrm{BEC}$
[25, 26]. In [27] the authors analyze threshold points for
$W^{\boldsymbol{u}}$ in the case of $\mathrm{BEC}$, fact that allows them to
propose sets of asymptotically ”good” channels. Recently, in [28] the authors
analyzed the Bhattacharyya parameter of polar codes for the $\mathrm{BEC}$
using network reliability theory. They have proposed simple approximations of
${\mathcal{B}\left(W^{\boldsymbol{u}}\right)}$. These were used to determine
sub-intervals of $[0,1]$ where polar codes coincide with Reed-Muller codes.
They have also managed to determine new sets of asymptotically ”good” channel.

###  1.1 Polar codes are strongly decreasing monomial codes

Polar codes over the $\mathrm{BEC}$ satisfy an order relation that is finer
than $\preceq.$ Hence, we define another order relation $\preceq_{d}$ on the
set of monomials on $m$ variables
$\mathcal{M}_{m}=\\{\bm{1},x_{0},\dots,x_{m-1},x_{0}x_{1},\dots,x_{0}x_{1}\dots
x_{m-1}\\}$, coming closer to the $\leq$ relation, i.e., we have

$\forall f,g\in\mathcal{M}_{m}\quad f\preceq g\Rightarrow
f\preceq_{d}g\Rightarrow f\leq g.$

The relation $\preceq_{d}$ allows to compare monomials with equal degrees that
were not comparable with respect to $\preceq$, e.g.,
$x_{1}x_{2}\preceq_{d}x_{0}x_{3}.$ The idea of $\preceq_{d}$ came from the
link between the set of monomials of degree $d$ in $\mathcal{M}_{m}$ and the
set of partitions/Young diagrams inside the $d\times(m-d)$ grid (see
Proposition 3.7.8 in [3]). From that, looking at order relations on partitions
came as a natural idea, and the most common one is the dominance order [29].
The order $\preceq_{d}$ is exactly defined as the dominance order on
partitions inside a fixed grid.

The main result in this section can be stated as follows

######  Theorem.

Polar codes over the Binary Erasure Channel are strongly decreasing monomial
codes.

In the proof of this theorem we will need to demonstrate two useful properties
of this new order

  * •

given two monomials in $f,g\in\mathcal{M}_{m}$ such that $f\preceq_{d}g$ then
for any multiples $fh,gh$ with $\gcd(h,f)=1$ and $\gcd(g,h)=1$ we have
$fh\preceq_{d}gh,$ where $\gcd(f,g)$ denotes the greatest common divisor of
$f,g$.

  * •

two particular monomials are the key ingredients in the proof,
$x_{1}x_{2}\preceq_{d}x_{0}x_{3}.$ We show that for all
$p\in[0,1],{\mathcal{B}\left(W^{x_{1}x_{2}}\right)}(p)\leq{\mathcal{B}\left(W^{x_{0}x_{3}}\right)}(p)$,
and in general that any pair of monomials of degree 2 $f,g$, satisfying
$f\preceq_{d}g$ has the property for all
$p\in[0,1],{\mathcal{B}\left(W^{f}\right)}(p)\leq{\mathcal{B}\left(W^{g}\right)}(p).$

Even though $\preceq_{d}$ get us closer to the ultimate order relation $\leq$
we know that $\preceq_{d}$ is a partial order relation. $\preceq_{d}$ seems to
perform as well as the order relation from [23], being much simpler to
describe and analyze that the order in [23]. Also, in [23] the authors
determine new order relations based on some hypothesis which are not
algebraically easy to express, and which are to be tested each time we change
the parameters of the code.

###  1.2 Average reliability of synthetic channels

Hence, we are still left with elements that are not comparable and for which
we need to compute ${\mathcal{B}\left(W^{\boldsymbol{u}}\right)}.$ In order to
overcome this issue we propose an alternative solution. Suppose that the
erasure probability of the channel $p$ changes with respect to the uniform
distribution over the closed interval $[0,1].$ Instead of constructing, for
each $p$, the corresponding polar code, we propose to construct the best polar
code in average. More exactly, we consider the average reliability of the
synthetic channels $W^{\boldsymbol{u}}$,
$\mathrm{Avr}(W^{\boldsymbol{u}})=\int_{0}^{1}{\mathcal{B}\left(W^{\boldsymbol{u}}\right)}dp$,
and choose those $\boldsymbol{u}$ that minimize this quantity. As the average
reliability induces a total order relation (see Figure 1) there is only one
polar code for a given dimension and length. It is the linear code that
minimizes the average error probability for all $p\in[0,1].$ Hence, it might
be less efficient than polar codes designed for a particular value of $p$ but
it has the best performance in average.

(a) $m=5$

(b) $m=7$

(c) $m=9$

Figure 1: Average Bhattacharyya parameter. On the x-axis are the integer
values of the binary vectors $\boldsymbol{u}\in\\{0,1\\}^{m}$, and on the
y-axis are the values
$\mathrm{Avr}({\mathcal{B}\left(W^{\boldsymbol{u}}\right)}).$

The preorder
$\boldsymbol{u}\leq_{\mathrm{Avr}}\boldsymbol{v}\Leftrightarrow\mathrm{Avr}({W^{\boldsymbol{u}}})\leq\mathrm{Avr}({W^{\boldsymbol{v}}})$
induces a complementarity property with respect to the integral operator over
$[0,1]$ as defined in [30, 31] in case of two-terminal networks. We retrieve a
similar property, i.e.,
$\mathrm{Avr}({W^{\boldsymbol{u}}})=1-\mathrm{Avr}\left(W^{\overline{\boldsymbol{u}}}\right),$
where $\overline{\boldsymbol{u}}$ is the bit-wise complement of
$\boldsymbol{u}$, in the context of monomial codes. Our simulations have shown
that, considering the relation $\leq_{\mathrm{Avr}}$ in the set of the
synthetic channels, in each sub-interval $(i/10,(i+1)/10)$, for $0\leq i\leq
9$, we have a rough proportion of $2^{m}/10$ binary vectors $\boldsymbol{u}.$
So, roughly speaking an uniform distribution could be used to approximate the
number of $\boldsymbol{u}$ inside each sub-interval, with respect to
$\mathrm{Avr}.$ However, our result is not constructive, in the sense that it
does not fully characterize exactly the $\boldsymbol{u}$ that belong to a
specific interval. An answer to this question might provide an extremely
efficient method for constructing polar codes and give much more insight on
the synthetic channels $W^{\boldsymbol{u}}.$

####  1.2.1 Threshold points for sharp transitions

Determining the threshold point of
${\mathcal{B}\left(W^{\boldsymbol{u}}\right)}$ is in general a difficult task
[32, 27]. In [27] the authors analyze a particular synthetic channel
$W^{(1^{i}0^{m-1})}$, for which asymptotic threshold points were determined.
The conditions on $i$ and $m$ were further improved in [23]. Based on some
basic notions and facts from network theory we determine an exact formula for
the average reliability of $W^{(1^{i}0^{m-1})}$. The main result is

######  Theorem.

Let $\boldsymbol{u}=(1^{i}0^{m-i}).$ Then

$\mathrm{Avr}\left(W^{\boldsymbol{u}}\right)=1-\dfrac{1}{\binom{2^{i}+2^{i-m}}{2^{i}}}$
(1)

This allows us to determine the exact threshold point of this particular
channel. Moreover, we demonstrate that for any $i\leq
m-\log_{2}(m)-\log_{2}(\log_{2}(m))$ the channel $W^{(1^{i}0^{m-i})}$ has an
average Bhattacharyya parameter that tends to zero when $m$ goes to infinity,
i.e., $W^{(1^{i}0^{m-i})}$ is asymptotically ”good” in average. Another
consequence of our formula is that for any monomial
$g\preceq_{d}x_{m-i+1}\dots x_{m}$ with $i\leq\log_{2}(\log_{2}(m))$ is such
that $\mathrm{Avr}(W^{g})$ tends to zero when $m$ goes to infinity.

Another significant implication of our result is that any synthetic channel in
the $\mathcal{RM}(i,m)$ is asymptotically ”good” in average, for any
$i\leq\log_{2}(\log_{2}(m)).$

$\preceq_{\mathrm{w}}$$\preceq$$\preceq_{d}$$\leq$$\leq_{\mathrm{Avr}}$$\beta$[4][17][4][15][15]hereherehere
Figure 2: Order ($\preceq_{\mathrm{w}},\preceq,\preceq_{d},\leq$) and pre-
order relations ($\leq_{\mathrm{Avr}}$) for monomials codes over the
$\mathrm{BEC}$. The connections in red are the results coming from this
article. The dotted edge from $\beta$ to $\leq$ represents an order relation
that is valid only for a sub-interval of $[0,1].$

##  2 Background and preliminary results

Let us begin by listing some of the usual notations from coding theory that
are going to be used in this article. $\mathbb{F}_{2}$ will denote the finite
field with two elements $\\{0,1\\}.$ Let $k,n$ be two strictly positive
integers and $k\leq n.$ A code $\mathscr{C}$ of length $n$ and dimension $k$
is a vector sub-space of $\mathbb{F}_{2}^{n}$ of dimension $k.$ In this
article, we focus out attention on a particular family or linear codes, namely
monomial codes. $W$ will be used to denote a communication channel with binary
input $x\in\mathbb{F}_{2}$ and output from an alphabet $y\in\mathcal{Y}.$ In
particular, we will focus on $\mathrm{BEC}(p)$, where the output is
$\mathcal{Y}=\\{0,1,?\\}$, $?$ denoting an erasure and $p$ being the erasure
probability. For a more detailed reading of the subject we recommend [33, 34].

###  2.1 Monomial codes

Monomial codes are a special class of structured codes. Informally, any code
that admits a basis, in which each vector is the evaluation of a monomial, is
called a monomial code. In general, monomial codes have a predefined length,
i.e., $2^{m}.$ Many of the notations, definitions, properties, and results
presented in this section are taken from [3].

In this article, binary vectors of length $m$ will be denoted using bold small
letters, e.g., $\boldsymbol{u}=(u_{0},\dots,u_{m-1})\in\mathbb{F}_{2}^{m}$,
with the convention that bits are ordered from left to right, $u_{0}$ being
the least significant bit. We also define the bit-wise complement of
$\boldsymbol{u}\in\\{0,1\\}$ by
$\overline{\boldsymbol{u}}=\bm{1_{m}}\oplus\boldsymbol{u}$ (as in [4]), where
$\bm{1_{m}}$ is the all-ones vector. The set
$\\{\boldsymbol{u}\in\mathbb{F}_{2}^{m}\\}$ will be ordered in a natural
manner, using the mapping

$(u_{0},\dots,u_{m-1})\rightarrow u=\sum_{i=0}^{m-1}u_{i}2^{i},$

and the natural order on the integers. Notice that we compute the value $u$
regardless of the fact that $u_{i}\in\mathbb{F}_{2}.$ Notice that the relation
between $\boldsymbol{u}$ and $\overline{\boldsymbol{u}}$ induces
$u+\overline{u}=2^{m}-1$.

We consider multivariate polynomials and monomials defined over the polynomial
ring
$\mathbb{R}_{m}={\mathbb{F}_{2}[x_{0},x_{1},\dots,x_{m-1}]}/{(x_{0}^{2}-x_{0},\dots,x_{m-1}^{2}-x_{m-1})}.$
The usual operators will be employed, i.e., for $f,g\in\mathbb{R}_{m}$, we
denote by $\deg{f}$ the degree of $f$, $\gcd(f,g)$ the greatest common divisor
of $f$ and $g$. $f/g$ denotes the quotient of $f$ and $g$.

######  Notation 1.

Let $m$ be a strictly positive integer. We denote

  * •

monomials:
$\boldsymbol{x}^{\boldsymbol{u}}=x_{0}^{u_{0}}\cdots{}x_{m-1}^{u_{m-1}},$
where $\boldsymbol{u}\in\mathbb{F}_{2}^{m}.$

  * •

support of a monomial: $\text{\rm ind}(g)=\\{l_{1}\,\dots,l_{s}\\}$ , where
$g=x_{l_{1}}\dots x_{l_{s}}$ and $0\leq l_{1}<l_{2}\dots<l_{s}\leq m-1.$

  * •

a subset of the support of a monomial:
$g_{[0,s]}=\gcd(g,\prod_{i=0}^{s}x_{i}).$

  * •

the set of monomials:
$\mathcal{M}_{m}\stackrel{{\scriptstyle\text{def}}}{{=}}\left\\{\boldsymbol{x}^{\boldsymbol{u}}~{}|~{}\boldsymbol{u}=(u_{0},\dots,u_{m-1})\in\mathbb{F}_{2}^{m}\right\\}.$

######  Proposition 1 ([35]).

Let $g\in\mathbb{R}_{m}$ and order the elements in $\mathbb{F}_{2}^{m}$ with
respect to the decreasing index order. Define the evaluation function

$\begin{array}[h]{ccccc}\mathbb{R}_{m}&\to&\mathbb{F}_{2}^{2^{m}}\\\
g&\mapsto&\mathsf{ev}(g)=\big{(}g(\boldsymbol{u})\big{)}_{\boldsymbol{u}\in\mathbb{F}_{2}^{m}}\end{array}$

Then $\mathsf{ev}$ is a bijection defining an isomorphism between the vector
spaces $(\mathbb{R}_{m},+,\cdot)$ and $(\mathbb{F}_{2}^{n},+,\cdot).$

Now, we are ready to define the concept of monomial codes.

######  Definition 1 (Monomial code).

Let $I\subseteq\mathcal{M}_{m}$ be a finite set of monomials in $m$ variables.
The linear code defined by $I$ is the vector subspace
$\mathscr{C}(I)\subseteq\mathbb{F}_{2}^{2^{m}}$ generated by
$\\{\mathsf{ev}(f)~{}|~{}f\in I\\}$ that is called _monomial code_.

######  Proposition 2 ([3]).

For all $I\subseteq\mathcal{M}_{m}$ the dimension of the monomial code
$\mathscr{C}(I)$ is equal to $|I|$.

######  Remark 1.

The $r^{th}$ order Reed-Muller code
$\mathcal{RM}(r,m)\stackrel{{\scriptstyle\text{def}}}{{=}}\big{\\{}\mathsf{ev}(g)~{}|~{}g\in\mathbb{R}_{m},\deg
g\leq r\big{\\}}$ is a monomial code with dimension
$k=\sum_{i=0}^{r}\binom{m}{i}.$

###  2.2 Polar codes

In order to define polar codes we have to introduce the concept of synthetic
channels. Consider the channel transformation
$W\rightarrow(W_{2}^{(0)},W_{2}^{(1)})$ defined in the following manner.

######  Definition 2 (Synthetic channels).

Let $W$ be a BDMC with output alphabet $\mathcal{Y}$and
$x_{1},x_{2}\in\mathbb{F}_{2}$ be the inputs and $y_{1},y_{2}\in\mathcal{Y}$
be the outputs of two copies of $W.$ Define two new channels

$\displaystyle{W^{(1)}}(y_{1},y_{2}|x_{2})$
$\displaystyle\stackrel{{\scriptstyle def}}{{=}}$
$\displaystyle\frac{1}{2}\sum_{x_{1}\in\mathbb{F}_{2}}W(y_{1}|x_{1})W(y_{2}|x_{1}\oplus
x_{2})$ $\displaystyle{W^{(0)}}(y_{1},y_{2},x_{2}|x_{1})$
$\displaystyle\stackrel{{\scriptstyle def}}{{=}}$
$\displaystyle\frac{1}{2}W(y_{1}|x_{1})W(y_{2}|x_{1}\oplus x_{2}).$

For any $\boldsymbol{u}=(u_{0},\dots,u_{m-1})\in\\{0,1\\}^{m}$ we define
$W^{\boldsymbol{u}}=((W^{u_{m-1}})^{\dots})^{u_{0}}$ as in [4]. Also, we
extend the notation to monomials, by $W^{f}_{m}=W^{\boldsymbol{u}}$ where
$f=\boldsymbol{x}^{\boldsymbol{u}}\in\mathcal{M}_{m}.$ We are using the index
$m$ in $W^{f}_{m}$ to precisely identify the number of variables on which $f$
is expressed. For example, if $\boldsymbol{u}=(1,0,0,1,1)$ we have
$W^{f}_{5}=W^{x_{0}x_{3}x_{4}}_{5}={{\left(W^{x_{4}}_{1}\right)}^{x_{0}x_{3}}_{4}}={{\left({{\left(W^{x_{4}}_{1}\right)}^{x_{3}}_{1}}\right)}^{x_{0}}_{3}}.$

######  Definition 3.

Let $W$ be a BDMC with output alphabet $\mathcal{Y}.$ Then the Bhattacharyya
parameter of the channel $W$ is

${\mathcal{B}\left(W\right)}=\sum_{y\in\mathcal{Y}}\sqrt{W(y|0)W(y|1)}.$ (2)

######  Remark 2.

Let $W$ be a $\mathrm{BEC}(p)$ then we have that
${\mathcal{B}\left(W^{x_{0}}\right)}={\mathcal{B}\left(W^{(1)}\right)}=2p-p^{2}$
and
${\mathcal{B}\left(W^{\bm{1}}\right)}={\mathcal{B}\left(W^{(0)}\right)}=p^{2}.$

######  Definition 4.

The polar code of length $n=2^{m}$ and dimension $k$ devised for the channel
$W$ is the linear code obtained by selecting the set of $k$ synthetic channels
with the smallest ${\mathcal{B}\left(W^{\boldsymbol{u}}\right)}$ values among
all $\boldsymbol{u}\in\\{0,1\\}^{m}$.

Moreover, we define the relation

$f\leq
g\Leftrightarrow\boldsymbol{u}\leq\boldsymbol{v}\Leftrightarrow{\mathcal{B}\left(W^{{\boldsymbol{u}}}\right)}(p)\leq{\mathcal{B}\left(W^{{\boldsymbol{v}}}\right)}(p),\forall
p\in[0,1].$ (3)

The relation (3) is called _universal_ , i.e., two monomials $f,g$ satisfying
$f\leq g$ are always comparable for any $p$ and any $m.$ This property can be
used when constructing polar codes by storing a table with all such monomials.
However, there might be several monomials bigger than $f$ which are not
comparable pairwise (see for example [4, 14]). Indeed, one can easily verify
that $\leq$ is a well-defined order relation (reflexive, anti-symmetric, and
transitive), and thus, induces a poset on the set of monomials. In some
particular cases, the order $\leq$ becomes total (all elements are ordered in
a chain), e.g., when $W=\mathrm{BEC}$ and $m\leq 4$. However, in general
$\leq$ is a partial order, even in the case of $W=\mathrm{BEC}$ (starting from
$m=5$), as pointed out in [11, 28, 3].

######  Proposition 3.

Let $m\geq 5$ be an integer and $W=\mathrm{BEC}.$ Then
$\\{\mathcal{M}_{m},\leq\\}$ is a poset.

For simplification, when we refer to ordering the Bhattacharyya parameters we
will just write
${\mathcal{B}\left(W^{{\boldsymbol{u}}}\right)}\leq{\mathcal{B}\left(W^{{\boldsymbol{v}}}\right)}.$

###  2.3 Weakly decreasing and decreasing monomial codes

######  Definition 5.

Let $f$ and $g$ be two monomials in $\mathcal{M}_{m}.$

  * •

The $\preceq_{\mathrm{w}}$ order between $f$ and $g$ is defined as

$f\preceq_{\mathrm{w}}g\quad\text{iff}\quad f|g.$

  * •

The $\preceq$ order between $f$ and $g$ is defined as

    * –

when $\deg(f)=\deg(g)=s$ and $f=x_{i_{1}}\dots x_{i_{s}}$, $g=x_{j_{1}}\dots
x_{j_{s}}$ we have

$f\preceq g\quad\text{iff}\quad\forall\;1\leq\ell\leq s\quad i_{\ell}\leq
j_{\ell}.$

    * –

when $\deg(f)<\deg(g)$ we have

$f\preceq g\quad\text{iff}\quad\exists
g^{*}\in\mathcal{M}_{m}\;\text{s.t.}\;f\preceq g^{*}\preceq_{\mathrm{w}}g.$

The two order relations $\preceq_{\mathrm{w}}$ and $\preceq$ are well defined.
$\preceq_{\mathrm{w}}$ was already used in the case of polar codes but in a
completely different context by Mori and Tanaka in [17]. In their case the
purpose was to tighten the bounds of the error block probability of a polar
code designed for the $\mathrm{BEC}$ family.

Notice that $\preceq_{\mathrm{w}}$ is weaker than $\preceq$, meaning that
$\forall f,g\in\mathcal{M}_{m}f\preceq_{\mathrm{w}}g\Rightarrow f\preceq g.$
The converse is not always true: taking, for example, $f=x_{0}x_{2}$ and
$g=x_{1}x_{2}$ it follows by definition that $f\preceq g$ but
$f\not\preceq_{\mathrm{w}}g.$ We also remark that $\bm{1}$ is the smallest
element both for $\preceq$ and for $\preceq_{\mathrm{w}}$, and we have

$\bm{1}\preceq x_{0}\preceq x_{1}\preceq\dots\preceq x_{m-1}.$

######  Definition 6.

Let $f$ and $g$ be two monomials in $\mathcal{M}_{m}$ such that $f\preceq g$
and $I\subset\mathcal{M}_{m}.$

  * •

We define the closed interval
$[f,g]_{\preceq}=\\{h\in\mathcal{M}_{m}\;|\;f\preceq h\preceq g\\}.$

  * •

$I\in\mathcal{M}_{m}$ is called a decreasing set if and only if ($f\in I$ and
$g\preceq f$) implies $g\in I$.

  * •

Let $I\in\mathcal{M}_{m}$ be a decreasing set. Then $\mathscr{C}(I)$ is called
decreasing monomial code.

Polar codes were recently related to network theory. In [28] the authors make
a connection between the Bhattacharyya parameter of a synthetic channel and
the reliability polynomial of a two-terminal network. Following on the same
path, we introduce in the next subsection all the required preliminaries in
reliability and network theory.

###  2.4 Two-terminal networks

######  Definition 7.

Let $n$ be a strictly positive integer. We say that $\bm{N}$ is a two-terminal
network (2TN) of size $n$ if $\bm{N}$ is a network made of $n$ identical
devices, that has two distinct terminals: an input $S$, and an output $T$.

To any $\bm{N}$ we associate three parameters: width ($w$), length ($l$), and
size ($n$), where $w$ is the size of a “minimal cut” separating $S$ from $T$,
and $l$ is the size of a “minimal path” from $S$ to $T$. The size of $\bm{N}$
satisfies

$n\geq wl$ (4)

(see Theorem 3 in [36]). When $n=wl$ we say that $\bm{N}$ is a minimal 2TN
[36].

The composition of $\bm{N}_{1}$ and $\bm{N}_{2}$ can be defined as in [36].
The resulting network is obtained by replacing each device in $\bm{N}_{1}$ by
a copy of $\bm{N}_{2}$. We will denote a composition by $\bm{C}$, the simplest
possible being two devices in series $\bm{C}^{(0)}$, and two devices in
parallel $\bm{C}^{(1)}$. The composition of $\bm{C}^{(0)}$ with $\bm{C}^{(1)}$
is $\bm{C}^{\boldsymbol{u}}=\bm{C}^{(0)}\bullet\bm{C}^{(1)}$, where
$\boldsymbol{u}=(0,1)$. The set of all $2^{m}$-size compositions will be
denoted by $\mathcal{C}_{2^{m}}$, and the set of all compositions of width
$2^{i}$ and length $2^{m-i}$ by $\mathcal{C}_{2^{i},2^{m-i}}$ (see Figure
3(b)).

######  Proposition 4 ([37]).

Let $m>0$ and $\bm{C}^{\boldsymbol{u}}\in\mathcal{C}_{2^{m}}.$ Then
$\bm{C}^{\boldsymbol{u}}$ is a minimal 2TN of size $2^{m},$ length
$l=2^{m-|\boldsymbol{u}|}$ and width $w=2^{|\boldsymbol{u}|}.$ We also have
$\mathcal{C}_{2^{m}}=\bigcup_{i=0}^{m}\mathcal{C}_{2^{i},2^{m-i}}.$

######  Theorem 1 ([11]).

There is a natural bijection between $\mathcal{C}_{2^{m}}$ and the set of all
$W^{\boldsymbol{u}}$, for any fixed positive integer $m.$

In figure 3 we illustrate the bijection between the two aforementioned sets.
More significant is the equality between the reliability polynomial of a
composition $\bm{C}^{\boldsymbol{u}}$ and the Bhattacharyya parameter of
$W^{\boldsymbol{u}}$, fact that is visible from figure 3(b) and proved in the
next paragraph.

##### Reliability polynomial

The reliability of $\bm{N}$ is defined as the probability that $S$ and $T$ are
connected (also known as $s,t$-connectivity) [38]. One of the most common
hypothesis considered in network theory is that devices are uniformly and
identically suppose to close with a probability $p\in[0,1].$ Hence, the
reliability of $\bm{N}$, denoted by $\mathrm{Rel}(\bm{N};p)$, can be expressed
as a polynomial

$\displaystyle\mathrm{Rel}(\bm{N};p)$
$\displaystyle=\sum\nolimits_{i=0}^{n}N_{i}(\bm{N})\;p^{i}(1-p)^{n-i}.$ (5)

(a) $W^{\boldsymbol{u}}$ and ${\mathcal{B}\left(W^{\boldsymbol{u}}\right)}$

(b) $\mathcal{C}_{3}$

Figure 3: Combined circuit as defined by Arikan [1], the Bhattacharyya
parameter of the corresponding synthetic channels and the compositions in
$\mathcal{C}_{3}.$

The coefficients $N_{i}(\bm{N})$ represent the number of paths from $S$ to $T$
of length $i$. Several properties regarding the coefficients $N_{i}(\bm{N})$,
as well as complementarity relations between a 2TN $\bm{N}$ and its dual
$\bm{N}$, are detailed in [30].

###  2.5 Bhattacharyya parameters and reliability polynomials

######  Theorem 2 ([11]).

Let $m>0$ , $\boldsymbol{u}\in\\{0,1\\}^{m}$, and $W=\mathrm{BEC}(p)$

${\mathcal{B}\left(W^{{\boldsymbol{u}}}\right)}(p)=\mathrm{Rel}(\bm{C}^{\boldsymbol{u}};p)$
(6)

where $\mathrm{Rel}(\bm{C}^{(0)};p)=p^{2}$ and
$\mathrm{Rel}(\bm{C}^{(1)};p)=1-(1-p)^{2}$.

######  Proposition 5 ([23]).

Let $m>0$ and $\boldsymbol{u}\in\\{0,1\\}^{m}.$ Then

${\mathcal{B}\left(W^{\overline{\boldsymbol{u}}}\right)}(p)=1-{\mathcal{B}\left(W^{{\boldsymbol{u}}}\right)}(1-p).$
(7)

This condition expresses the duality of the two corresponding networks, namely
$\bm{C}^{\overline{\boldsymbol{u}}}$ is the dual of
$\bm{C}^{{\boldsymbol{u}}}$ (see [30, 11]). Notice that by (7) one has to
analyze only $\boldsymbol{u}$ with $|\boldsymbol{u}|\leq m/2$.

##  3 Polar codes are strongly decreasing monomial code over the BEC

######  Definition 8.

The $\preceq_{d}$ order between $f$ and $g$ is defined as

  * •

when $\deg(f)=\deg(g)=s$ and $f=x_{i_{1}}\dots x_{i_{s}}$, $g=x_{j_{1}}\dots
x_{j_{s}}$ we have

$f\preceq_{d}g\quad\text{iff}\quad\forall\ell\in\\{1,\dots,s\\}\text{we
have}\sum\limits_{k=0}^{\ell}i_{s-k}\leq\sum\limits_{k=0}^{\ell}j_{s-k}.$

  * •

when $\deg(f)<\deg(g)$ we have

$f\preceq_{d}g\quad\text{iff}\quad\exists
g^{*}\in\mathcal{M}_{m}\;\text{s.t.}\;f\preceq_{d}g^{*}\preceq_{\mathrm{w}}g.$

######  Definition 9.

Let $f$ and $g$ be two monomials in $\mathcal{M}_{m}$ such that $f\preceq g$
and $I\subset\mathcal{M}_{m}.$

  * •

We define the closed interval
$[f,g]_{\preceq_{d}}=\\{h\in\mathcal{M}_{m}\;|\;f\preceq_{d}h\preceq_{d}g\\}.$

  * •

$I\in\mathcal{M}_{m}$ is called a strongly decreasing set if and only if
($f\in I$ and $g\preceq_{d}f$) implies $g\in I$.

  * •

Let $I\in\mathcal{M}_{m}$ be a strongly decreasing set. Then $\mathscr{C}(I)$
is called strongly decreasing monomial code.

######  Lemma 1.

The order $\preceq_{d}$ is a well-defined order relation and
$\\{\mathcal{M}_{m},\preceq_{d}\\}$ forms a Poset.

The proof of this lemma is trivial.

Figure 4: The two order relations $\preceq$ and $\preceq_{d}$ for $m=4.$

######  Remark 3.

Notice that $x_{i_{1}}\dots x_{i_{s}}\preceq x_{j_{1}}\dots x_{j_{s}}$ implies
that $x_{i_{1}}\dots x_{i_{s}}\preceq_{d}x_{j_{1}}\dots x_{j_{s}}.$ The
converse is no longer true, take for example the monomials $x_{0}x_{3}$ and
$x_{1}x_{2}.$

######  Proposition 6.

Let $f$ and $g$ be two monomial having the same degree and $x_{h}$ be such
that $x_{h}\not|f$ and $x_{h}\not|g.$ Then we have

$f\preceq_{d}g\text{ iff }x_{h}f\preceq_{d}x_{h}g.$ (8)

###### Proof.

Let $f=x_{i_{1}}\dots x_{i_{s}}$ and $g=x_{j_{1}}\dots x_{j_{s}}$ with
$f\preceq_{d}g.$ Also, let $f^{*}=fx_{h}$ and $g^{*}=gx_{h}.$ There are
several cases to be examined here:

  * •

If $x_{j_{s}}\preceq x_{h}$ or $x_{h}\preceq x_{i_{1}}$ then the relation
$f^{*}\preceq_{d}g^{*}$ can easily be verified by using the definition of
$\preceq_{d}.$

  * •

If there is an integer $r\in\\{1,\dots,s\\}$ s.t. $x_{i_{r}}\preceq
x_{h}\preceq x_{i_{r+1}}$ and $x_{j_{r}}\preceq x_{h}\preceq x_{j_{r+1}}$ then
the relation $f^{*}\preceq_{d}g^{*}$ can easily be verified as in the previous
step.

  * •

If there are two distinct integers $r,t\in\\{1,\dots,s\\}$ s.t.
$x_{i_{r}}\preceq x_{h}\preceq x_{i_{r+1}}$ and $x_{j_{t}}\preceq x_{h}\preceq
x_{j_{t+1}}$ then two cases have to be considered.

    * –

If $t<r$ then we have $x_{i_{h}}\preceq x_{j_{t+1}}\preceq\dots\preceq
x_{j_{r}}$ and $x_{i_{t+1}}\preceq\dots\preceq x_{i_{r}}\preceq x_{h}$, which
implies the following ordering

$x_{i+{t+1}}\preceq\dots\preceq x_{i_{r}}\preceq x_{h}\preceq
x_{j_{t+1}}\preceq\dots\preceq x_{j_{r}}.$ (9)

Combining equation (9) with the definition of $\preceq_{d}$ we obtain the
desired result, i.e., $f^{*}\preceq_{d}g^{*}.$

    * –

$t>r$ then we have $x_{i_{h}}\preceq x_{i_{r+1}}\preceq\dots\preceq x_{i_{t}}$
and $x_{j_{r+1}}\preceq\dots\preceq x_{j_{t}}\preceq x_{h}$ which implies the
following ordering

$x_{j+{r+1}}\preceq\dots\preceq x_{j_{t}}\preceq x_{h}\preceq
x_{i_{r+1}}\preceq\dots\preceq x_{i_{t}}.$ (10)

Now, since $x_{h}\preceq x_{i_{t}}$ it might be possible to have $j_{s}+\dots
j_{t+1}+h<i_{s}+\dots+i_{t+1}+i_{t}$, which implies a violation of the partial
sum conditions in the definition of $\preceq_{d}.$ If the next partial sum
changes the sign, i.e., $j_{s}+\dots j_{t+1}+h+j_{t}\geq
i_{s}+\dots+i_{t+1}+i_{t}+i_{t-1}$, by setting
$\Delta_{t+1}=(j_{s}-i_{s})+\dots+(j_{t+1}-i_{t+1})$ we have the following
inequalities

$\displaystyle\Delta_{t+1}+h-i_{t}$ $\displaystyle<0$ (11)
$\displaystyle\Delta_{t+1}+h-i_{t}+j_{t}-i_{t-1}$ $\displaystyle\geq 0.$ (12)

This implies

$\Delta_{t+1}+h<i_{t}\leq\Delta_{t+1}+h+j_{t}-i_{t-1}.$ (13)

However, since $j_{t}<i_{t-1}$ the equation (13) becomes impossible, which
completes the proof.

∎

In particular, notice that if $f,g$ are co-prime, i.e., $\gcd{(f,g)}\neq 1$,
then

$f\preceq_{d}g\text{ iff }{f}/{\gcd{(f,g)}}\preceq_{d}{g}/{\gcd{(f,g)}}.$ (14)

Remark that when the condition on variable $x_{h}$ is not satisfied, the
result does not hold, e.g., $x_{2}x_{3}\preceq_{d}x_{1}x_{4}$, but
$x_{1}x_{2}x_{3}$ and $x_{1}x_{4}$ are not comparable with respect to
$\preceq_{d}.$ Before we get to our main theorem of this section, the
following lemma is required.

######  Lemma 2.

Let $f,g\in\mathcal{M}_{m},\deg{f}=\deg{g}=2$, such that $f\preceq_{d}g.$ Then
${\mathcal{B}\left(W^{f}_{m}\right)}\leq{\mathcal{B}\left(W^{g}_{m}\right)}.$

###### Proof.

Let $f=x_{i_{1}}x_{i_{2}}$ and $g=x_{j_{1}}x_{j_{2}}.$ If $\gcd(f,g)\neq 1$
then $f\preceq g$, which implies
${\mathcal{B}\left(W^{f}_{m}\right)}\leq{\mathcal{B}\left(W^{g}_{m}\right)}.$

Now suppose $\gcd(f,g)=1$, and let $j_{1}-i_{1}\leq j_{2}-i_{2}.$ Denote
$\epsilon=j_{1}-i_{1}.$ By definition of $\preceq_{d}$ and $\preceq$ we have

$f=x_{i_{1}}x_{i_{2}}\preceq_{d}x_{i_{1}-1}x_{i_{2}+1}\preceq_{d}\dots\preceq_{d}x_{j_{1}}x_{i_{2}+\epsilon}\preceq
x_{j_{1}}x_{j_{2}}=g.$ (15)

If we prove
$x_{i_{1}}x_{i_{2}}\preceq_{d}x_{i_{1}-1}x_{i_{2}+1}\Rightarrow{\mathcal{B}\left(W^{x_{i_{1}}x_{i_{2}}}_{m}\right)}\leq{\mathcal{B}\left(W^{x_{i_{1}-1}x_{i_{2}+1}}_{m}\right)}$
the proof is finished. By definition, one can easily notice that
${\mathcal{B}\left(W^{x_{1}x_{2}}_{4}\right)}\leq{\mathcal{B}\left(W^{x_{0}x_{3}}_{4}\right)}\Leftrightarrow{\mathcal{B}\left(W^{x_{i_{1}}x_{i_{2}}}_{m}\right)}\leq{\mathcal{B}\left(W^{x_{i_{1}-1}x_{i_{2}+1}}_{m}\right)}.$
Hence we are left to prove that
${\mathcal{B}\left(W^{x_{1}x_{2}}_{4}\right)}\leq{\mathcal{B}\left(W^{x_{0}x_{3}}_{4}\right)}.$
We have that
${\mathcal{B}\left(W^{x_{0}x_{3}}_{4}\right)}(p)=1-(1-(1-(1-p)^{2})^{4})^{2}$
and ${\mathcal{B}\left(W^{x_{1}x_{2}}_{4}\right)}(p)=(1-(1-p^{2})^{4})^{2}.$

By writing the two polynomials in the Bernstein basis, and using Theorem 2 we
have
${\mathcal{B}\left(W^{x_{1}x_{2}}_{4}\right)}=\mathrm{Rel}(\bm{C}^{(0,1,1,0)})$
and
${\mathcal{B}\left(W^{x_{0}x_{3}}_{4}\right)}=\mathrm{Rel}(\bm{C}^{(1,0,0,1)})$
with

$\displaystyle N_{i}(\bm{C}^{(0,1,1,0)})$
$\displaystyle=0,0,0,0,16,192,1008,3040,5828,7456,6552,4048,1788,560,120,16,1$
$\displaystyle N_{i}(\bm{C}^{(1,0,0,1)})$
$\displaystyle=0,0,0,0,32,320,1456,3984,7042,8400,7000,4176,1804,560,120,16,1$

As $N_{i}(\bm{C}^{(0,1,1,0)})\leq N_{i}(\bm{C}^{(1,0,0,1)})$ for all
$i\in\\{0,\dots,16\\}$ we conclude the proof. ∎

######  Corollary 1.

Let $f=x_{i_{1}}x_{i_{2}}$ and $g=x_{j_{1}}x{j_{2}}$ s.t. $f\preceq_{d}g.$
Then for any monomial $h=x_{l_{1}}\dots x_{l_{t}}$ satisfying
$i_{1}<l_{1}<\dots<l_{t}<i_{2}$ we have $fh\preceq_{d}gh$ and
${\mathcal{B}\left(W^{fh}_{m}\right)}\leq{\mathcal{B}\left(W^{gh}_{m}\right)}.$

######  Theorem 3.

Polar codes over the Binary Erasure Channel are strongly decreasing monomial
codes.

###### Proof.

The proof is based on two induction steps. First the parameter $m$ is fixed
and we prove that the result holds for any $1\leq s\leq m$. Secondly we use
induction on $m$.

Firstly, fix $m$ and use an induction argument on the degree of monomial,
namely on $s.$ We also suppose that $\gcd{(f,g)}=1.$ For $s=1$ we have that
$\preceq=\preceq_{d}$ so the result is obvious. For $s=2$ use Lemma 2.

Now suppose that for any $f\preceq_{d}g$ with $\deg{f}=\deg{g}=s-1$ we have
that
${\mathcal{B}\left(W^{f}_{m}\right)}\leq{\mathcal{B}\left(W^{g}_{m}\right)}.$
Let $f=x_{i_{1}}\dots x_{i_{s}}$ and $g=x_{j_{1}}\dots x_{j_{s}}$ such that
$g\preceq_{d}f$ with the usual convention $i_{1}<\dots<i_{s}$ and
$j_{1}<\dots<j_{s}$. Then we have two cases. Either if
$f/x_{i_{s}}\preceq_{d}g/x_{j_{s}}$ or if $x_{i_{1}}\leq x_{j_{1}}$ then we
have
${\mathcal{B}\left(W^{f}_{m}\right)}\leq{\mathcal{B}\left(W^{g}_{m}\right)}$.
Indeed, in the first case we have that

$\displaystyle{\mathcal{B}\left(W^{f}_{m}\right)}$
$\displaystyle={\mathcal{B}\left({{\left(W^{x_{i_{s}}}_{m-j_{s-1}-1}\right)}^{f/x_{i_{s}}}_{j_{s-1}+1}}\right)}\leq{\mathcal{B}\left({{\left(W^{x_{j_{s}}}_{m-j_{s-1}-1}\right)}^{f/x_{i_{s}}}_{j_{s-1}+1}}\right)}$
$\displaystyle\leq{\mathcal{B}\left({{\left(W^{x_{j_{s}}}_{m-j_{s-1}-1}\right)}^{g/x_{j_{s}}}_{j_{s-1}+1}}\right)}={\mathcal{B}\left(W^{g}_{m}\right)}.$

In the second case when $x_{i_{1}}\leq x_{j_{1}}$ the proof works in the same
way. If we are not in the previous case it means that $j_{1}<i_{1}$ and
$i_{s}<j_{s}.$ We know that there is $l\in\\{1,\dots,s-1\\}$ for which
$i_{l}>j_{l}.$ First we treat the two extreme cases $l=1$ or $l=s-1.$ If $l=1$
this implies that $j_{k}\geq i_{k}$ for all $k>1$. Let
$\delta=\min\\{j_{2}-i_{2},i_{1}-j_{1}\\}.$ Then

$f=x_{i_{1}}x_{i_{2}}\dots
x_{i_{s}}\preceq_{d}x_{i_{1}-\delta}x_{i_{2}+\delta}x_{i_{3}}\dots
x_{i_{s}}\preceq_{d}x_{j_{1}}\dots x_{j_{s}}=g.$

In this case, either $x_{i_{1}-\delta}=x_{j_{1}}$ or
$x_{i_{2}+\delta}=x_{j_{2}}.$ Hence, by Lemma 2 and using the order relation
$\preceq$ we obtain

$\displaystyle{\mathcal{B}\left(W^{f}_{m}\right)}$
$\displaystyle={\mathcal{B}\left({{\left(W^{f/(x_{i_{1}}x_{i_{2}})}_{m-j_{2}-1}\right)}^{x_{i_{2}}x_{i_{1}}}_{j_{2}+1}}\right)}\leq{\mathcal{B}\left({{\left(W^{f/(x_{i_{1}}x_{i_{2}})}_{m-j_{2}-1}\right)}^{x_{i_{2}+\delta}x_{i_{1}-\delta}}_{j_{2}+1}}\right)}$
$\displaystyle\leq{\mathcal{B}\left({{\left(W^{x_{i_{s}}\dots
x_{i_{3}}}_{m-j_{2}-1}\right)}^{x_{j_{2}}x_{j_{1}}}_{j_{2}+1}}\right)}\leq{\mathcal{B}\left({{\left(W^{x_{j_{s}}\dots
x_{j_{3}}}_{m-j_{2}-1}\right)}^{x_{j_{2}}x_{j_{1}}}_{j_{2}+1}}\right)}={\mathcal{B}\left(W^{g}_{m}\right)}.$

If $l=s-1$, by putting $\delta=i_{s-1}-j_{s-1}$ and taking into account that
$\delta\leq j_{s}-i_{s}$ we obtain

$\displaystyle{\mathcal{B}\left(W^{f}_{m}\right)}$
$\displaystyle={\mathcal{B}\left({{\left(W^{x_{i_{s}}x_{i_{s-1}})}_{m-j_{s-2}-1}\right)}^{f/(x_{i_{s}}x_{i_{s-1}})}_{j_{s-2}+1}}\right)}\leq{\mathcal{B}\left({{\left(W^{x_{i_{s}+\delta}x_{i_{s-1}-\delta})}_{m-j_{s-2}-1}\right)}^{f/(x_{i_{s}}x_{i_{s-1}})}_{j_{s-2}+1}}\right)}$
$\displaystyle={\mathcal{B}\left({{\left(W^{x_{i_{s}+\delta}x_{j_{s-1}})}_{m-j_{s-2}-1}\right)}^{x_{i_{s-2}}\dots
x_{i_{1}}}_{j_{s-2}+1}}\right)}\leq{\mathcal{B}\left({{\left(W^{x_{j_{s}}x_{j_{s-1}})}_{m-j_{s-2}-1}\right)}^{x_{j_{s-2}}\dots
x_{j_{1}}}_{j_{s-2}+1}}\right)}={\mathcal{B}\left(W^{g}_{m}\right)}.$

When $1<l<s-1$ suppose that $i_{s}-j_{l}<j_{l+1}-i_{s}$ and denote by
$\delta_{l,s}=i_{s}-j_{l}.$ Using the definition of $\preceq_{d}$ we have

$h=x_{j_{1}}\dots x_{j_{l}+\delta_{l,s}}x_{j_{l+1}-\delta_{l,s}}\dots
x_{j_{s}}\preceq_{d}\dots\preceq_{d}x_{j_{1}}\dots
x_{j_{l}+1}x_{j_{l+1}-1}\dots x_{j_{s}}\preceq_{d}x_{j_{1}}\dots x_{j_{s}}=g.$

Notice that $h=x_{j_{1}}\dots x_{j_{l-1}}x_{i_{s}}x_{j_{l+1}-i_{s}+j_{l}}\dots
x_{j_{s}}.$ Next, we prove that $f\preceq_{d}h.$ Since
$\gcd{(f,h)}=x_{i_{s}}$, we can use Lemma 6 and demonstrate
${f}/{x_{i_{s}}}\preceq_{d}{h}/{x_{i_{s}}}$, i.e.,
$x_{i_{1}}\dots x_{i_{s-1}}\preceq_{d}x_{j_{1}}\dots
x_{j_{l-1}}x_{j_{l+1}-i_{s}+j_{l}}x_{j_{l+2}}\dots x_{j_{s}}.$ As,

$x_{i_{l+1}}\preceq\dots\preceq x_{i_{s}}\preceq
x_{j_{l+1}}\preceq\dots\preceq x_{j_{s}},$ (16)

we obtain $x_{i_{l+1}}\dots x_{i_{s-1}}\preceq_{d}x_{j_{l+2}}\dots x_{j_{s}}$,
simply by verifying

$\forall\;t\in\\{0,\dots,s-l-2\\}\quad\sum\limits_{k=0}^{t}{i_{s-1-k}}\leq\sum\limits_{k=0}^{t}{j_{s-k}}.$
(17)

The next partial sums inequalities,

$(i_{k}+\dots+i_{l-1})+i_{l}+i_{l+1}+\dots+i_{s-1}<(j_{k}+\dots+j_{l-1})+j_{l+1}-i_{s}+j_{l}+j_{l+2}+\dots+j_{s}$
(18)

are verified from the relation $f\preceq_{d}g.$ So we check the partial sums
step by step:

  1. 1.

$i_{s-1}<i_{s}<j_{l+1}<j_{s}$ and thus $x_{i_{s-1}}\preceq_{d}x_{j_{s}}$

  2. 2.

$i_{s-1}+i_{s-1}<j_{s-1}+j_{s}$ and thus
$x_{i_{s}-2}x_{i_{s-1}}\preceq_{d}x_{j_{s-1}}x_{j_{s}}$

  3. 3.

$\dots$

  4. 4.

$i_{l+1}+\dots+i_{s-1}<j_{l+2}+\dots+j_{s}$ and thus $x_{i_{l+1}}\dots
x_{i_{s-1}}\preceq_{d}x_{j_{l+2}}\dots x_{j_{s}}$

  5. 5.

$i_{l}+i_{l+1}+\dots+i_{s-1}<j_{l+1}-i_{s}+j_{l}+j_{l+2}+\dots+j_{s}$ by
definition of $f\preceq_{d}g$ and thus $x_{i_{l}}\dots
x_{i_{s-1}}\preceq_{d}x_{j_{l+1}-i_{s}+j_{l}}\dots x_{j_{s}}$

  6. 6.

$\dots$

Hence we have that ${f}/{x_{i_{s}}}\preceq_{d}{h}/{x_{i_{s}}}$ which implies,
using the induction hypothesis, that
${\mathcal{B}\left(W^{f/x_{i_{s}}}_{m}\right)}\leq{\mathcal{B}\left(W^{h/x_{i_{s}}}_{m}\right)},$
from which we deduce
${\mathcal{B}\left(W^{f}_{m}\right)}\leq{\mathcal{B}\left(W^{h}_{m}\right)}.$
Also,

$\displaystyle{\mathcal{B}\left(W^{h}_{m}\right)}$
$\displaystyle={\mathcal{B}\left(\left(\left(W^{x_{j_{s}}\dots
x_{j_{l+2}}}\right)^{x_{j_{l+1-\delta_{l,s}}}x_{j_{l+\delta_{l,s}}}}\right)^{x_{j_{l-1}}\dots
x_{j_{1}}}\right)}$
$\displaystyle={\mathcal{B}\left(\left((W^{*})^{x_{j_{l+1-\delta_{l,s}}}x_{j_{l+\delta_{l,s}}}}\right)^{x_{j_{l-1}}\dots
x_{j_{1}}}\right)}\leq{\mathcal{B}\left(\left((W^{*})^{x_{j_{l+1}}x_{j_{l}}}\right)^{x_{j_{l-1}}\dots
x_{j_{1}}}\right)}$
$\displaystyle={\mathcal{B}\left(\left(\left(W^{x_{j_{s}}\dots
x_{j_{l+2}}}\right)^{x_{j_{l+1}}x_{j_{l}}}\right)^{x_{j_{l-1}}\dots
x_{j_{1}}}\right)}={\mathcal{B}\left(W^{g}_{m}\right)}.$

Secondly, we use induction on the number of variables $m.$ For the first
values of $m$, i.e., $m\leq 4$ it is straightforward to check the result.

Let $f=x_{i_{1}}\dots x_{i_{s}}$ and $g=x_{j_{1}}\dots x_{j_{s}}$ such that
$g\preceq_{d}f$ with the usual convention $i_{1}<\dots<i_{s}$ and
$j_{1}<\dots<j_{s}$. The following cases are possible

  * •

If $i_{s}=j_{s}=m$ then we have
$W^{f}_{m+1}={{\left(W^{f_{m}}_{1}\right)}^{f_{[0,m-1]}}_{m}}$ and
$W^{g}_{m+1}={{\left(W^{g_{m}}_{1}\right)}^{g_{[0,m-1]}}_{m}}.$ Since
$f_{[0,m-1]}\preceq_{d}g_{[0,m-1]}$ we have by the induction hypothesis

${\mathcal{B}\left({{\left(W^{x_{m}}_{1}\right)}^{f_{[0,m-1]}}_{m}}\right)}\leq{\mathcal{B}\left({{\left(W^{x_{m}}_{1}\right)}^{g_{[0,m-1]}}_{m}}\right)}.$
(19)

  * •

Else, by the definition of the order we necessary have $j_{s}>i_{s}.$ We also
have that

$h=x_{j_{1}}\dots x_{j_{s-1}+1}x_{j_{s}-1}\preceq_{d}x_{j_{1}}\dots
x_{j_{s-1}}x_{j_{s}}=g.$

Which implies that
${\mathcal{B}\left(W^{h}_{m+1}\right)}\leq{\mathcal{B}\left(W^{g}_{m+1}\right)}.$
In the same time notice that $f\preceq_{d}h$ and $\text{\rm ind}(f),\text{\rm
ind}(h)\in\\{0,\dots,m-1\\}.$ Therefore we obtain

${\mathcal{B}\left(W^{f}_{m+1}\right)}\leq{\mathcal{B}\left(W^{h}_{m+1}\right)}\leq{\mathcal{B}\left(W^{g}_{m+1}\right)}.$
(20)

∎

##  4 Average Reliability of the synthetic channels

The geometric approach of the properties of a function by means of its
subgraph and/or epigraph generated useful mathematical tools from the very
beginning of the theory of functions. Measure, intersection, support and shape
properties lead to applications in various domains: optimization, shape
description and recognition, etc. Here we propose a geometric approach in the
field of polar coding. Recently, the concept of _average reliability_ was
introduced and analyzed in the context of all terminal reliability [39].

As the synthetic channels cannot be totally ordered [4, 23], we propose a
different method to define the optimality of a synthetic channel. For that we
will check how reliable is a channel in average, i.e., we define

######  Definition 10.

Let $m$ be a strictly positive integer and $\boldsymbol{u}\in\\{0,1\\}^{m}$.
The average reliability of $W^{\boldsymbol{u}}$ is

$\mathrm{Avr}\left(W^{\boldsymbol{u}}\right)=\int\limits_{0}^{1}{\mathcal{B}\left(W^{\boldsymbol{u}}\right)}(p)dp.$

Moreover, we define the relation $\leq_{\mathrm{Avr}}$

$\boldsymbol{u}\leq_{\mathrm{Avr}}\boldsymbol{v}\Leftrightarrow\mathrm{Avr}({W^{\boldsymbol{u}}})\leq\mathrm{Avr}({W^{\boldsymbol{v}}})$

This notion of optimality has a meaning in the following context. Imagine that
the communication channel is a $\mathrm{BEC}$ with variable erasure
probability, coming from different physical reasons. This means that either we
choose a different polar code in function of the variations of $p$ and in this
case we obtain the best performance for each instance, or we choose a polar
code and hope that in average it performs in an optimal way. The former
strategy comes with the cost of computing for each value of $p$ the
corresponding polar code, as for the later the cost is minimal since we only
construct a polar code.

###  4.1 Properties

######  Lemma 3.

The relation $\leq_{\mathrm{Avr}}$ is reflexive and transitive. In other
words, $\leq_{\mathrm{Avr}}$ is a pre-order relation.

Our simulations have shown that up to $m=13$, $\leq_{\mathrm{Avr}}$ is also
antisymmetric. However, this property might not be true in general. Indeed,
one can easily find two distinct polynomials with integer coefficients defined
over $[0,1]$ with values in $[0,1]$, such that their integrals are equal.
Nonetheless, we can overcome this by applying the following procedure.

######  Remark 4.

Let $\boldsymbol{u}\equiv_{\mathrm{Avr}}\boldsymbol{v}$ if and only if
$\mathrm{Avr}({\mathcal{B}\left(W^{\boldsymbol{u}}\right)})=\mathrm{Avr}({\mathcal{B}\left(W^{\boldsymbol{v}}\right)}).$
Let us extend the relation $\leq_{\mathrm{Avr}}$ to the factor set
$\mathcal{M}_{m}/\equiv_{\mathrm{Avr}}$ naturally, using the relation between
class representatives. Then $\leq_{\mathrm{Avr}}$ is a total order relation
over $\mathcal{M}_{m}/\equiv_{\mathrm{Avr}}.$ Indeed, one can easily check
that $\leq_{\mathrm{Avr}}$ is antisymmetric over
$\mathcal{M}_{m}/\equiv_{\mathrm{Avr}}.$

(a) $m=5$

(b) $m=7$

(c) $m=9$

Figure 5: Sorted $\mathrm{Avr}({\mathcal{B}\left(W^{\boldsymbol{u}}\right)})$
for all $\boldsymbol{u}\in\\{0,1\\}^{m}.$

######  Lemma 4.

Let $m$ be a strictly positive integer, $n=2^{m}$, and
$\boldsymbol{u}\in\\{0,1\\}^{m}.$ Then

$\mathrm{Avr}\left(W^{\boldsymbol{u}}\right)=\dfrac{1}{n+1}\sum\limits_{i=2^{m-|\boldsymbol{u}|}}^{n}\dfrac{N_{i}(\bm{C}^{\boldsymbol{u}})}{\binom{n}{i}}.$
(21)
$\mathrm{Avr}\left(W^{\boldsymbol{u}}\right)+\mathrm{Avr}\left(W^{\overline{\boldsymbol{u}}}\right)=1.$
(22)

######  Proposition 7.

Let $m$ be a strictly positive integer and $\boldsymbol{u},\boldsymbol{v}$ be
two binary vectors of length $m$ such that $\boldsymbol{u}\leq\boldsymbol{v}$.
Then

$\boldsymbol{u}\leq\boldsymbol{v}\Rightarrow\mathrm{Avr}\left(W^{\boldsymbol{u}}\right)\leq\mathrm{Avr}\left(W^{\boldsymbol{v}}\right).$
(23)

Table 1: Average reliability of the synthetic channels

$m=2$
---
0 | 1 | 2 | 3 |  |  |  |  |  |  |  |  |  |  |  |
$0.20$ | $0.47$ | $0.53$ | $0.80$ |  |  |  |  |  |  |  |  |  |  |  |
$m=3$
0 | 1 | 2 | 4 | 3 | 5 | 6 | 7 |  |  |  |  |  |  |  |
$0.11$ | $0.29$ | $0.34$ | $0.41$ | $0.59$ | $0.66$ | $0.71$ | $0.89$ |  |  |  |  |  |  |  |
$m=4$
0 | 1 | 2 | 4 | 8 | 3 | 5 | 6 | 9 | 10 | 12 | 7 | 11 | 13 | 14 | 15
$0.06$ | $0.16$ | $0.20$ | $0.24$ | $0.30$ | $0.38$ | $0.44$ | $0.48$ | $0.52$ | $0.56$ | $0.62$ | $0.70$ | $0.76$ | $0.80$ | $0.84$ | $0.94$

In Table 1 we compute the $\mathrm{Avr}\left(W^{\boldsymbol{u}}\right)$ all
the binary vectors $\boldsymbol{u}\in\\{0,1\\}^{m}$ for $m\in\\{2,3,4\\}.$
Notice that in this case Proposition 7 applies, since we know that up to $m=4$
the synthetic channels can be totally ordered over the $\mathrm{BEC}$ [3, 23].
Starting from $m=5$ this property is no longer true. When $\boldsymbol{u}$ and
$\boldsymbol{v}$ are no longer comparable, i.e., there is $p_{0}\in(0,1)$ such
that
${\mathcal{B}\left(W^{\boldsymbol{u}}\right)}(p_{0})={\mathcal{B}\left(W^{\boldsymbol{v}}\right)}(p_{0})$,
we can still decide whether in average $\boldsymbol{u}$ is optimal compared
with $\boldsymbol{v}.$ The set of non comparable pairs
$(\boldsymbol{u},\boldsymbol{v})$ for $m=5$ is
$\\{(3,16),(12,17),(7,20),(7,24),(11,24),(14,19),(15,28)\\}.$ Notice that half
of the pairs are coming from duality, i.e., if
$(\boldsymbol{u},\boldsymbol{v})$ are not comparable then
$(\overline{\boldsymbol{u}},\overline{}\boldsymbol{v})$ are also non-
comparable. However, these are ordered with respect to average reliability.
The average reliability for the first 4 non-comparable pairs are
$(0.221,0.216),(0.396,0.383),$ $(0.4712,0.4710),(0.4712,0.5288)$. Hence, for
$m=5$ the ordering with respect to the average reliability is
$0,1,2,4,8,16,3,5,6,9,10,17,12,18,20,7,24$, and the rest can be completed by
symmetry.

######  Example 1.

The ordering induced by the average reliability.

  * •

$m=5$

$0,\underbrace{1,2,4,8,16}_{\mathcal{RM}(1,5)},\overbrace{3,5,6,9,10,17,12,18,20}^{\mathcal{RM}(2,5)},\underbrace{7}_{\mathcal{RM}(3,5)},\overbrace{24}^{\mathcal{RM}(2,5)}$

  *   * •

$m=6$

$0,\underbrace{1,2,4,8,16}_{\mathcal{RM}(1,6)},\overbrace{3,5}^{\mathcal{RM}(2,6)},\underbrace{32}_{\mathcal{RM}(1,6)},\overbrace{6,9,10,17,12,18,33,20}^{\mathcal{RM}(2,6)},\underbrace{7}_{\mathcal{RM}(3,6)},\overbrace{34,24}^{\mathcal{RM}(2,6)},\underbrace{11}_{\mathcal{RM}(3,6)},\overbrace{36}^{\mathcal{RM}(2,6)},$
$\underbrace{13,19,14}_{\mathcal{RM}(3,6)},\overbrace{40}^{\mathcal{RM}(2,6)},\underbrace{21}_{\mathcal{RM}(3,6)},\overbrace{48}^{\mathcal{RM}(2,6)},\underbrace{22,35,25,37,26,38,28,41}_{\mathcal{RM}(3,6)}$

Our simulations have shown that, considering the relation
$\leq_{\mathrm{Avr}}$ in the set of the synthetic channels, in each sub-
interval $(i/10,(i+1)/10])$, for $0\leq i\leq 9$, we have a rough proportion
of $2^{m}/10$ binary vectors $\boldsymbol{u}.$ So, roughly speaking an uniform
distribution could be used to approximate the number of $\boldsymbol{u}$
inside each sub-interval (illustrated in Figure 5), with respect to
$\mathrm{Avr}$ (see Table 2 for $5\leq m\leq 11.$)

Table 2: Number of $\boldsymbol{u}\in\\{0,1\\}^{m}$ that satisfy $\mathrm{Avr}({\mathcal{B}\left(W^{\boldsymbol{u}}\right)})\in(i/10,(i+1)/10]$, for $0\leq i<5$, $\epsilon_{m}=2^{m-4}/10.$ $m$ | $(0,0.1]$ | $(0.1,0.2]$ | $(0.2,0.3]$ | $(0.3,0.4]$ | $(0.4,0.5]$ | $[\lfloor 2^{m}/10-\epsilon_{m}\rfloor,\lceil 2^{m}/10+\epsilon_{m}\rceil]$
---|---|---|---|---|---|---
5 | 2 | 3 | 4 | 4 | 3 | $[3,4]$
6 | 5 | 7 | 6 | 8 | 6 | $[6,7]$
7 | 11 | 13 | 14 | 13 | 13 | $[12,14]$
8 | 23 | 25 | 27 | 27 | 26 | $[24,28]$
9 | 49 | 51 | 50 | 55 | 51 | $[48,55]$
10 | 99 | 104 | 98 | 107 | 104 | $[97,109]$
11 | 199 | 209 | 204 | 204 | 208 | $[194,218]$

###  4.2 Relation to $\beta$-expansion

$\beta$-expansion [15] is a well-known method for an efficient construction of
Polar codes. Hence, it is with no surprise that our results on average
reliability determine possible more refined choices of the variable $\beta.$
Let us begin by defining the method.

$\beta(\boldsymbol{u})=\sum\limits_{i=0}^{m-1}u_{i}\beta^{i}$ (24)

In [15] the authors proved that for any $\beta\in(1,\infty)$ the order induced
by $\beta$ on the sequence of synthetic channels respects the order relation
$\preceq.$ In particular this means that if
$\boldsymbol{u}\preceq\boldsymbol{v}$ then
$\beta(\boldsymbol{u})\leq\beta(\boldsymbol{v})$ and this for any value of
$\beta>1.$ Some values of $\beta$ are of high interest, in particular
$\beta=2^{1/4}$, when $W$ is designed for Additive White Gaussian Noise
(AWGN). In the case of AWGN, the authors in [15] proposed a procedure in which
an interval for $\beta$ is determined, interval that converges to a value
close to $2^{1/4}.$ Notice that in [15] the order induced by $\beta$ is not
valid for any Signal to Noise Ratio value, but it tries to cover as much as
possible the interval $[0,1].$ A natural question that one could raise is
whether there is a $\beta$-expansion for the average reliability, i.e., is
there a real value $\beta$ such that $\beta$ and $\mathrm{Avr}$ are identical
over the set of binary vectors of length $m.$ There is a significant
difference between the two relations. In our case, not only that $W$ is a BEC
but also the pre-order induced by the average reliability is total over
$\mathcal{M}_{m}/\equiv_{\mathrm{Avr}}$ and holds for the entire interval
$[0,1].$

######  Remark 5.

By computer simulations one can easily prove that for $m\leq 5,$ there is
$\beta\in(1,\infty)$ such that the order induced by $beta$ and the pre-order
induced by the average reliability coincide. It can be done by simply tacking
$\beta=1.22$.

######  Conjecture 1.

For $m>6$ we did not find a value of $\beta$ for which the two aforementioned
relations are equal. Moreover, for $\beta\sim 1.22$ the number of elements
having similar mutual relations with respect to the two relations is minimized
(see Table 3).

Table 3: Number of pairs $(\boldsymbol{u},\boldsymbol{v})$ satisfying $\mathrm{Avr}({\mathcal{B}\left(W^{\boldsymbol{u}}\right)})\leq\mathrm{Avr}({\mathcal{B}\left(W^{\boldsymbol{v}}\right)})$ for which $\not\exists\beta\in(1,\infty)$ s.t. $\beta(\boldsymbol{u})\leq\beta(\boldsymbol{v}).$ $m$ | $\beta$ | number of incompatible pair of elements | $2^{m}$
---|---|---|---
4 | $(1,1.32]$ | – | 16
5 | $(1.18,1.22]$ | – | 32
6 | $1.22$ | 2 | 64
7 | $1.22$ | 10 | 128
8 | $1.22$ | 36 | 256
9 | $1.22$ | 99 | 512

###  4.3 Threshold points of the binary erasure polarization sub-channels

The fact that when $m$ goes to infinity the Bhattacharyya polynomial has a
sharp transition from zero to one when $m$ goes to infinity has already been
proven ([32]).

######  Lemma 5.

$\lim\limits_{m\to\infty}{\mathcal{B}\left(W^{\boldsymbol{u}}\right)}=\left\\{\begin{array}[]{cc}0&p\in[0,p_{0}(\boldsymbol{u}))\\\
1&p\in(p_{0}(\boldsymbol{u}),1]\\\ \end{array}\right.$ (25)

However, finding the point $p_{0}(\boldsymbol{u})$ where this transition holds
is not trivial (see [27, 15]). Here we will use the average reliability to
determine this point for some specific channels.

######  Lemma 6.

$\lim\limits_{m\to\infty}\mathrm{Avr}\left(W^{\boldsymbol{u}}\right)=1-p_{0}(\boldsymbol{u}).$
(26)

A particular interesting channel analyzed in [27, 23] is the synthetic channel
$W^{(1^{i}0^{m-i})}.$ More exactly, the authors analyze the sharp transition
of $W^{(1^{i}0^{m-i})}$ from $0$ to $1$ when $m$ tends to infinity, in
function of the limit ${i}/{m-i}.$ Here, we will give an exact formula for the
average reliability of $W^{(1^{i}0^{m-i})}$. This result combined with Lemma 6
will allow us to obtain a finer approximation of $p_{0}(\boldsymbol{u}).$ To
achieve our goal, we will look at the corresponding 2TN, namely at
$\bm{C}^{(1^{i}0^{m-i})}$. For simplification we use $l=2^{m-i},w=2^{i}$ and
$n=2^{m}.$ Notice that

$\mathrm{Rel}\left(\bm{C}^{(1^{i}0^{m-i})};p\right)=1-(1-p^{l})^{w}.$ (27)

######  Theorem 4.

$\mathrm{Rel}\left(\bm{C}^{(1^{i}0^{m-i})};p\right)=\sum\limits_{i=l}^{n}\sum\limits_{j=1}^{\lfloor\frac{i}{l}\rfloor}(-1)^{j+1}\binom{w}{j}\binom{n-jl}{n-i}p^{i}(1-p)^{n-i}.$
(28)

###### Proof.

In order to prove our result we need to demonstrate that $\forall\;l\leq i\leq
n$

$N_{i}(\bm{C}^{(1^{i}0^{m-i})})=\sum\limits_{j=1}^{\lfloor\frac{i}{l}\rfloor}(-1)^{j+1}\binom{w}{j}\binom{n-jl}{n-i}$
(29)

The proof is based on an inclusion-exclusion argument. Denote by
$\mathcal{P}_{i}$ the set of paths of length $i$ from $S$ to $T$ for the
$\bm{C}^{(1^{i}0^{m-i})}$. This leads to
$\left|\mathcal{P}_{i}\right|=N_{i}(\bm{C}^{(1^{i}0^{m-i})}).$

Any path of length $i$ with $l\leq i$ is composed of at least one path of
length $l$, hence we have $w$ choices for fixing a path of length $l$ and
$\binom{n-l}{i}$ choices for the remaining positions. However, in the
$\binom{n-l}{i}$ choices we might count other $l$ length paths. Hence, we need
to subtract the over-counting, which is all the combinations of two length $l$
paths, i.e., $\binom{w}{2}$, times the number of choices for the remaining
positions, i.e., $\binom{n-2l}{i-2l}.$ Now, we need to add all the paths that
are composed of at least $3$ $l$ paths which equals
$\binom{w}{3}\binom{n-3l}{i-3l}.$ And so on till we reached the last level,
i.e.,
$\binom{w}{\lfloor\frac{i}{l}\rfloor}\binom{n-l\lfloor\frac{i}{l}\rfloor}{i-l\lfloor\frac{i}{l}\rfloor}.$

∎

######  Theorem 5.

$\mathrm{Avr}\left(W^{(1^{i}0^{m-i})}\right)=1-\dfrac{1}{\binom{2^{i}+2^{i-m}}{2^{i}}}$
(30)

###### Proof.

$\displaystyle\mathrm{Avr}\left(W^{\boldsymbol{u}}\right)$
$\displaystyle=\dfrac{1}{n+1}\sum\limits_{i=l}^{n}\dfrac{N_{i}(\bm{C}^{\boldsymbol{u}})}{\binom{n}{i}}=\dfrac{1}{n+1}\sum\limits_{i=l}^{n}\sum\limits_{j=1}^{\lfloor\frac{i}{l}\rfloor}(-1)^{j+1}\dfrac{\binom{w}{j}\binom{n-jl}{n-i}}{\binom{n}{i}}$
$\displaystyle=\dfrac{1}{n+1}\sum\limits_{j=1}^{w}\sum\limits_{i=jl}^{n}(-1)^{j+1}\dfrac{\binom{w}{j}\binom{n-jl}{n-i}}{\binom{n}{i}}=\dfrac{1}{n+1}\sum\limits_{j=1}^{w}\sum\limits_{i=jl}^{n}(-1)^{j+1}\dfrac{\binom{w}{j}\binom{i}{jl}}{\binom{n}{jl}}$
$\displaystyle=\dfrac{1}{n+1}\sum\limits_{j=1}^{w}(-1)^{j+1}\dfrac{\binom{w}{j}}{\binom{n}{jl}}\sum\limits_{i=jl}^{n}\binom{i}{jl}=\dfrac{1}{n+1}\sum\limits_{j=1}^{w}(-1)^{j+1}\dfrac{\binom{w}{j}\binom{n+1}{jl+1}}{\binom{n}{jl}}$
$\displaystyle=\sum\limits_{j=1}^{w}(-1)^{j+1}\binom{w}{j}\dfrac{1}{jl+1}=1-\sum\limits_{j=0}^{w}(-1)^{j}\binom{w}{j}\dfrac{1}{jl+1}=1-\dfrac{1}{\binom{\frac{n+1}{l}}{w}}$

∎

Strightforward, we have

######  Corollary 2.

$\mathrm{Avr}\left({W^{(0^{i}1^{m-i})}}\right)=\dfrac{1}{\binom{2^{i}+2^{i-m}}{2^{i}}}$
(31)

Based on Theorem 5 we can establish new classes of asymptotically ”good”
channels. For that we will need the following result.

######  Lemma 7.

$\displaystyle\lim\limits_{n\to\infty}\begin{pmatrix}\frac{n}{\log_{2}(n)(\log_{2}(\log_{2}(n)))}+\frac{1}{\log_{2}(n)(\log_{2}(\log_{2}(n)))}\\\
\frac{n}{\log_{2}(n)(\log_{2}(\log_{2}(n)))}\end{pmatrix}$ $\displaystyle=1.$
(32)
$\displaystyle\lim\limits_{n\to\infty}\begin{pmatrix}\frac{n}{\log_{2}(\log_{2}(n))}+\frac{1}{\log_{2}(\log_{2}(n))}\\\
\frac{n}{\log_{2}(\log_{2}(n))}\end{pmatrix}$ $\displaystyle=\infty.$ (33)
$\displaystyle\lim\limits_{n\to\infty}\begin{pmatrix}\frac{n}{\log_{2}(n)}+\frac{1}{\log_{2}(n)}\\\
\frac{n}{\log_{2}(n)}\end{pmatrix}$ $\displaystyle=2.$ (34)

Theorem 5, Lemma 7 and Lemma 6 imply the following result.

######  Corollary 3.

Let $m$ be a strictly positive integer and
$\boldsymbol{u}=\left(1^{i}0^{m-i}\right)$ Then

  * •

for any $i\leq m-\log_{2}(m)-\log_{2}(\log_{2}(m))$ we have
$p_{0}(\boldsymbol{u})\to 1$ and $p_{0}(\overline{\boldsymbol{u}})\to 0.$

  * •

for any $i\geq m-\log_{2}(\log_{2}(m))$ we have $p_{0}(\boldsymbol{u})\to 0$
and $p_{0}(\overline{\boldsymbol{u}})\to 1.$

Another direct consequence of our results is that for any $i\leq
m-\log_{2}(m)-\log_{2}(\log_{2}(m))$ the monomial $f=x_{0}\dots x_{i-1}$ is
highly reliable in average. Hence, all the monomials $g\preceq_{d}f$ are also
highly reliable in average, as their average reliability tends to zero when
$m$ goes to infinity. Also, $f$ becomes unreliable in average for $i\geq
m-\log_{2}(\log_{2}(m)).$ The values
$m-\log_{2}(m)-\log_{2}(\log_{2}(m))<i<m-\log_{2}(\log_{2}(m))$ are to be
considered in more details.

######  Corollary 4.

Let $m$ be a strictly positive integer and $i\leq\log_{2}(\log_{2}(m)).$ Then
for any $f\in\mathcal{M}_{m}$ with $f\preceq_{d}x_{m-i+1}\dots x_{m}$ we have
that $\mathrm{Avr}(W^{f})\to 0$ when $m\to\infty.$ In other words, any
synthetic channel in the $\mathcal{RM}(i,m)$ is asymptotically ”good” in
average.

##  5 Conclusions and Perspectives

A complete characterization of the Bhattacharyya parameter of synthetic
channels of a monomial code is an open problem that has attracted a lot of
attention in the last decade. Even for the particular case of Binary Erasure
Channel the question remains unanswered. However, the implications of such a
result are of high importance in coding theory, specially in polar coding. In
this article, we make a step forward by proposing an order relation
$\preceq_{d}$ that decreases the gap between state-of-the-art and the ultimate
partial order relation for the Battacharya parameter of synthetic channels.
The advantage of this approach is that our algebraic description is rather
easy to implement and analyze, compared to other order relations such as [23].
Simulations show that $\preceq_{d}$ is a valid order relation on Binary
Symmetric Channel, and a deeper inspection of [23] and our work, could
potentially determine an algebraic description that fits the latest results.

As the relations on the Bhattacharyya parameter are all partial orders, we
have proposed an alternative solution for ordering the synthetic channels. For
that, we have used the concept of average reliability, borrowed from the
network theory. Instead of the local evaluation of the Bhattacharyya
parameter, we propose a global one, by evaluating the integral, i.e., by
measuring its global average behavior. Hence, we rank the synthetic channels
using a pre-order relation $\leq_{\mathrm{Avr}}$, given by the value of the
integral. Our result is not constructive, in the sense that it does not fully
characterize the channels that belong to a specific interval. An answer to
this question might provide an extremely efficient method for constructing
polar codes and give much more insight on the synthetic channels
$W^{\boldsymbol{u}}.$

## Acknowledgements

V-F. Dragoi is supported by a grant of the Romanian Ministry of Education and
Research, CNCS- UEFISCDI, project number PN-III-P1-1.1-PD-2019-0285, within
PNCDI III.

## References

  * [1] Arıkan, E.  Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels.  IEEE Trans. Inform. Theory 2009, 55, 3051–3073.  doi:10.1109/TIT.2009.2021379.
  * [2] Bioglio, V.; Condo, C.; Land, I.  Design of Polar Codes in 5G New Radio.  IEEE Communications Surveys Tutorials 2020, early access, pp. 1–1.  doi:10.1109/COMST.2020.2967127.
  * [3] Dragoi, V.  Algebraic approach for the study of algorithmic problems coming from cryptography and the theory of error correcting codes.  PhD Thesis, Université de Rouen, Normandie, France, 2017.  [hal.archives:tel-01627324]
  * [4] Bardet, M.; Dragoi, V.; Otmani, A.; Tillich, J.  Algebraic properties of polar codes from a new polynomial formalism.  IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, 2016, pp. 230–234.  doi:10.1109/ISIT.2016.7541295.
  * [5] Rengaswamy, N.; Calderbank, R.; Newman, M.; Pfister, H.D.  Classical Coding Problem from Transversal $T$ Gates, 2020,  IEEE International Symposium on Information Theory, ISIT 2020, Los Angeles, CA, USA, 2020, pp. 1891–1896.
doi:10.1109/ISIT44484.2020.9174408.

  * [6] Rengaswamy, N.  Classical Coding Approaches to Quantum Applications, 2020, [arXiv:quant-ph/2004.06834].
  * [7] Krishna, A.; Tillich, J.P.  Magic state distillation with punctured polar codes, 2019, [arXiv:quant-ph/1811.03112].
  * [8] Bardet, M.; Chaulet, J.; Dragoi, V.; Otmani, A.; Tillich, J.P.  Cryptanalysis of the McEliece Public Key Cryptosystem Based on Polar Codes.  Post-Quantum Cryptography, PQCrypto 2016; Lecture Notes in Comput. Sci., pp. 118–143, vol. 9606, Springer, Cham.  doi:10.1007/978-3-319-29360-8˙9.
  * [9] Drăgoi, V.; Beiu, V.; Bucerzan, D.  Vulnerabilities of the McEliece Variants Based on Polar Codes.  In Innovative Security Solutions for Information Technology and Communications, SecITC 2018; Lecture Notes in Comput. Sci., pp. 376–390, vol. 11359, Springer Cham.  doi:10.1007/978-3-030-12942-2˙29.
  * [10] Bucerzan, D.; Dragoi, V.; Kalachi, H.T., Evolution of the McEliece Public Key Encryption Scheme.  In Innovative Security Solutions for Information Technology and Communications, SecITC 2017, Lecture Notes in Comput. Sci., pp. 129–149, vol. 10543, Springer Cham.  doi:10.1007/978-3-319-69284-5˙10.
  * [11] Drăgoi, V.F.; Beiu, V.  Fast Reliability Ranking of Matchstick Minimal Networks, 2019, [arXiv:cs.DM/1911.01153].
  * [12] Dragoi, V.; Cowell, S.; Beiu, V.  Ordering series and parallel compositions.  Proc. IEEE International Conference on Nanotechnology (IEEE-NANO); Cork, Ireland, 2018, pp. 1–4.  doi:10.1109/NANO.2018.8626408.
  * [13] Beiu, V.; Cowell, S.R.; Drăgoi, V.F.  On Posets for Reliability: How Fine Can They Be?  In Soft Computing Applications SOFA 2018, Advances in Intelligent Systems and Computing, 2021; pp. 115–129. vol 1221. Springer, Cham.  doi:10.1007/978-3-030-51992-6˙10.
  * [14] Mondelli, M.; Hassani, S.H.; Urbanke, R.  Construction of polar codes with sublinear complexity.  Proc. IEEE International Symposium on Information Theory (ISIT); Aachen, Germany 2017; pp. 1853–1857.  doi:10.1109/ISIT.2017.8006850.
  * [15] He, G.; Belfiore, J.; Land, I.; Yang, G.; Liu, X.; Chen, Y.; Li, R.; Wang, J.; Ge, Y.; Zhang, R.; Tong, W.  Beta-Expansion: A Theoretical Framework for Fast and Recursive Construction of Polar Codes.  Proc. IEEE Global Communications Conference (GLOBECOM); Singapore, Singapore 2017; pp. 1–6.  doi:10.1109/GLOCOM.2017.8254146.
  * [16] Tal, I.; Vardy, A.  How to Construct Polar Codes.  IEEE Trans. Inform. Theory 2013, 59, 6562–6582.  doi:10.1109/TIT.2013.2272694.
  * [17] Mori, R.; Tanaka, T.  Performance and construction of polar codes on symmetric binary-input memoryless channels.  IEEE Int. Symposium Inf. Theory - ISIT2009, Seoul, South Korea, pp. 1496–1500.  doi:10.1109/ISIT.2009.5205857.
  * [18] Mahdavifar, H.; El-Khamy, M.; Lee, J.; Kang, I.  On the construction and decoding of concatenated polar codes.  Proc. IEEE Int. Symposium Inf. Theory - ISIT2013; Istanbul, Turkey, pp. 952–956.  doi:10.1109/ISIT.2013.6620367.
  * [19] Korada, S.B.; Sasoglu, E.; Urbanke, R.L.  Polar Codes: Characterization of Exponent, Bounds, and Constructions.  IEEE Trans. Inform. Theory 2010, 56, 6253–6264.  doi:10.1109/TIT.2010.2080990.
  * [20] Afşer, H.; Deliç, H.  On the Channel-Specific Construction of Polar Codes.  IEEE Communications Letters 2015, 19, 1480–1483.  doi:10.1109/LCOMM.2015.2450213.
  * [21] Trifonov, P.; Trofimiuk, G.  A randomized construction of polar subcodes.  2017 IEEE Int. Symposium Inf. Theory - ISIT2017, Aachen, Germany, pp. 1863–1867.  doi:10.1109/ISIT.2017.8006852.
  * [22] Huang, L.; Zhang, H.; Li, R.; Ge, Y.; Wang, J.  AI Coding: Learning to Construct Error Correction Codes.  IEEE Transactions on Communications 2020, 68, 26–39.  doi:10.1109/TCOMM.2019.2951403.
  * [23] Wu, W.; Siegel, P.H.  Generalized Partial Orders for Polar Code Bit-Channels.  IEEE Transactions on Information Theory 2019, 65, 7114–7130.  doi:10.1109/TIT.2019.2930292.
  * [24] Saptharishi, R.; Shpilka, A.; Volk, B.L.  IEEE Transactions on Information Theory 2017, 63, 1954–1960.  doi:10.1109/TIT.2017.2671410.
  * [25] Kudekar, S.; Kumar, S.; Mondelli, M.; Pfister, H.D.; Sasoglu, E.; Urbanke, R.  Reed-Muller Codes Achieve Capacity on Erasure Channels.  IEEE Transactions on Information Theory 2017, PP, 1–1.  doi:10.1109/TIT.2017.2673829.
  * [26] Kumar, S.; Calderbank, R.; Pfister, H.D.  Beyond double transitivity: Capacity-achieving cyclic codes on erasure channels.  2016 IEEE Information Theory Workshop (ITW), Cambridge, UK, pp. 241–245.  doi:10.1109/ITW.2016.7606832.
  * [27] Ordentlich, E.; Roth, R.M.  On the Pointwise Threshold Behavior of the Binary Erasure Polarization Subchannels.  IEEE Transactions on Information Theory 2019, 65, 6044–6055.  doi:10.1109/TIT.2019.2920140.
  * [28] Drăgoi, V.F.; Beiu, V.  Studying the Binary Erasure Polarization Subchannels Using Network Reliability.  IEEE Communications Letters 2020, 24, 62–66.  doi:10.1109/LCOMM.2019.2947910.
  * [29] Stanley, R.P.  Enumerative Combinatorics; Cambridge University Press: Cambridge, NY, 2012.  doi:10.1017/CBO9781139058520
  * [30] Cristescu, G.; Drăgoi, V.F.  Cubic Spline Approximation of the Reliability Polynomials of Two Dual Hammock Networks.  Transylvanian Journal of Mathematics and Mechanics 2019, 11, 77–90.  url:19111208
  * [31] Cristescu, G.; Drăgoi, V.F.  Efficient approximation of two-terminal networks reliability polynomials using cubic splines.  IEEE Transactions on Reliability 2021, 1–11.  doi:10.1109/TR.2021.3049957.
  * [32] Mondelli, M.  From Polar to Reed-Muller Codes: Unified Scaling, Non-standard Channels, and a Proven Conjecture.  PhD thesis, Ecole Polytechnique Fédérale de Lausanne, 2016.  doi:10.5075/epfl-thesis-7164
  * [33] Richardson, T.; Urbanke, R.  Modern Coding Theory; Cambridge University Press, New York, NY, USA, 2008.  doi:10.1017/CBO9780511791338
  * [34] Roth, R.M.  Introduction to Coding Theory; Cambridge University Press: New York, NY, USA, 2006.  doi:10.1017/CBO9780511808968
  * [35] Carlet, C.  Boolean functions for cryptography and error correcting codes. In Boolean Models and Methods in Mathematics, Computer Science, and Engineering; Cambridge University Press: Cambridge, NY, 2010; chapter 8, pp. 257–397.  doi:10.1017/CBO9780511780448.011
  * [36] Moore, E.F.; Shannon, C.E.  Reliable circuits using less reliable relays - Part I.  Journal of the Franklin Institute 1956, 262, 191–208.  doi:10.1016/0016-0032(56)90559-2
  * [37] Drăgoi, V.; Cowell, S.R.; Beiu, V.; Hoară, S.; Gaşpar, P.  How Reliable are Compositions of Series and Parallel Networks Compared with Hammocks?  International Journal of Computers Communications & Control 2018, 13, 772–791.  doi:10.15837/ijccc.2018.5.3354
  * [38] Colbourn, C.J.  The Combinatorics of Network Reliability; Oxford University Press: New York, NY, 1987.  doi:10.5555/535891
  * [39] Brown, J.; Cox, D.; Ehrenborg, R.  The average reliability of a graph.  Discrete Applied Mathematics 2014, 177, 19 – 33.  doi:10.1016/j.dam.2014.05.048