##  1 Design, Environmental and Legislative Constraints

Constraints limit the capabilities of the aerial vehicle to perform its task
of package delivery. Khosiawan and Nielsen define three elements when
considering employing a UAV for a certain application; task, environment and
operation system [khosiawan_system_2016]. They describe the task as the
activity performed by the UAV, in this case, package delivery. The environment
is the surroundings and infrastructure where the UAV is situated such as the
landing zone and transit space. Finally, they define the operating system as
the design and infrastructure to enable the UAV to perform its task. This
includes the aerial manipulation device, landing gears, and sensors.

For this review, the constraints are classified into three groups; design,
environmental and legislative. Design constraints consist of physical
restrictions when engineering the vehicle. This can be further broken down
into the choice of the thrust generating mechanism, the trade-off this thrust
generating mechanism has on the components or size of the vehicle, and finally
the payload design. Environmental constraints consist of the physical
surroundings which dictate the difficulty and safety of traversing a certain
area. These factors determine the sensing capability and manoeuvrability of
the vehicle. Two major environments consist of both in-transit and landing
zones. Both with varying levels of obstacles, satellite signal and navigation
difficulty. Finally, legislative constraints consist of restrictions that are
enforced. This varies from the responsibility for the UAV system to the
guidelines for physical flight and social impact. These constraints are
illustrated in the tree diagram, Figure 1.

Figure 1: This figure illustrates the constraints used to compare different
techniques within the autonomous delivery UAV pipeline for their effect on
the: design, environment, and social factors

###  1.1 Design Constraints

To enable flight, thrust forces must be generated to offset the weight of the
aircraft. This thrust can be generated in various forms such as airflow over
an aerofoil, dynamic wings, or rotating propellers. The advantages and
disadvantages of these designs are discussed with a summary in Table 1. Then,
the size, weight and power of the components and design need to be considered.
Finally, the design of the payload needs to be considered which includes
geometry, gripping points, contents, and weight.

####  1.1.1 Thrust generating Mechanism

UAV sizes can vary dramatically; typically the most notable difference
surrounds the propulsion mechanism, and fuselage design
[hassanalian_classifications_2017, macrina_drone-aided_2020,
singhal_unmanned_2018]. Alternatively, UAVs can be classified by weight and
wingspan [hassanalian_classifications_2017]. Based on the propulsion
mechanism, UAVs can be classified into three main categories: fixed-wing,
rotary-wing and flapping-wing [shraim_survey_2018] as shown in Figure 2.

[Fixed-wing [cosyn_design_2007]] [Rotary-wing [heredia_control_2014]]
[Flapping-wing [nguyen_development_2018]] [Hybrid [phillips_flight_2017]]

Figure 2: Classification of common UAV designs used throughout the literature.

Fixed-wing aircraft, as the name suggests, consist of a rigid wing that is
used to generate lift from the aircraft’s forward motion. These types of
aircraft can also use a motor and propeller as their propulsion system. Due to
the aerodynamic efficiencies, fixed-wing UAVs have a long flight time and can
cover a wide range of environments. Because of this, fixed-wing vehicles can
carry large payloads for long distances, consuming less power compared to
other UAV designs. The disadvantage is the requirement of constant forward
motion to provide lift, and therefore fixed-wing vehicles do not have the
ability to be stationary and are less manoeuvrable.

Rotary-wing designs rely on rotors to produce lift and torque about the centre
of rotation. The most common rotary-wing designs come in the form of a
helicopter, which contains one rotor, or a multi-rotor such as a quadcopter,
hexacopter or octocopter. The torque generated from these motors causes
instability. For multi-rotor designs, rotors spin in symmetrically opposite
directions to offset this generated torque, whereas helicopters possess a tail
rotor. These vehicles do not require constant movement since the lift is
generated by the rotors, and therefore these vehicles can perform stationary
operations and can vertically take off and land easily. Alternatively, they
are able to perform aggressive manoeuvres such as within racing events
[culley_system_2020]. These manoeuvres, however, can lead to high energy
throughput.

Flapping-wing based designs take inspiration from birds or insects. The
propulsion mechanism consists of flexible and flapping wings which use an
actuated mechanism for the flapping motion [hassanalian_classifications_2017].
The flexible [nguyen_development_2018, phan_design_2017] and lightweight
[han_review_2021] wing properties are important for aerodynamic proficiency
and flight stability.

Hybrid designs combine fixed, rotary or flapping-wing vehicle concepts
together in an attempt to gain additional benefits. One example is the hybrid
fixed-wing vertical take-off and landing (VTOL) vehicle [gu_development_2017].
This vehicle has two independent propulsion systems for hover and level
flight. The aircraft takes off vertically using the lift force generated by
the rotors. Then while hovering, a push motor is used to gain forward momentum
allowing the aircraft to behave like a conventional fixed-wing UAV. Therefore,
this design benefits from the vertical lift-off from rotary-wing designs and
gains the added aerodynamic efficiencies and extended flight time of the
fixed-wing design. Other designs include tilt-wing [cetinsoy_design_2012],
tilt-rotor [chen_design_2020], tilt-body [ro_aerodynamic_2007], and ducted fan
[deng_aerodynamic_2020]. A comparison between all the designs discussed above
is shown in Table 1. For further analysis the reader can direct their
attention to [shraim_survey_2018].

Table 1: Comparison between rotary wings, fixed wings and flapping wings. The table illustrates the strengths and weaknesses of each design. | Rotary-Wing | Fixed-Wing | Flapping-Wing |  Hybrid
---|---|---|---|---
Top Speed | High | High | Low | High
Turning Radius | Low | Medium | Medium | Medium
Energy Consumption | High | Low | High | Medium
Complexity and Repair Cost | Medium | Low | High | High
Payload Capacity |  Medium |  Medium |  Low |  Medium
Accuracy of Delivery |  High |  Low |  Low |  High
Noise Pollution |  Medium |  Medium |  Low |  High
Vertical Takeoff |  Yes |  No |  Yes |  Yes
Hover Capability |  Yes |  No |  No |  Yes

Highly manoeuvrable vehicles can avoid obstacles and traverse more complicated
environments. Furthermore, global planners can consider a turning radius,
leading to more efficient routing and allowing for a broader range of
accessible routes. Fixed-wing vehicles tend to have large turning circles
compared to other designs due to their thrust-generating mechanism.
Comparably, rotary-wing designs can perform a range of manoeuvres, including
aggressive flight paths, enabled by the availability of multiple thrust-
generating components. It has been shown in the literature that quadrotors are
differentially flat under-actuated systems [faessler_differential_2018]. From
a motion planning perspective, this property enables better tracking
capabilities for aggressive flight. Reducing energy consumption increases the
travel time of the aerial delivery vehicle. Increasing this allows the vehicle
to visit either more customers or remote locations. Several studies have
compared the energy consumption of last-mile delivery for UAVs and lorries.
Stolaroff et al. analysed the impact of aerial delivery vehicles compared to
delivery trucks. The authors found that UAVs consumed less energy throughout
the delivery process than trucks. However, they also found an increased
requirement of warehouses storing packages due to the limited flight range.
Furthermore, more complex actuation is required, as discussed later, can lead
to more moving parts and in general higher costs associated with repair. Since
fixed-wing designs have fewer moving parts than rotary wing designs the number
of failure points increases, leading to higher long-term costs. Finally,
payload capacity depends on the payload’s size, weight and available space
within the vehicle’s frame. Larger thrust forces, using more powerful motors,
can allow for heavier payloads at the cost of more power consumption.
Furthermore, larger packages can impact aerodynamics and restrict component
placement.

####  1.1.2 The SWAP constraint

The capability of aerial vehicles are bound by the relationship between the
on-board computation, thrust generating mechanism, limited size and space, and
sensing capabilities. This is also known as the size, weight and power (SWAP)
trade-off [chung_survey_2018]. This relationship also limits the available
weight and size of a payload. Bulky payloads require more thrust to carry,
which requires more power. Furthermore, higher moments of inertia and a
greater offset of the centre of mass can lead to unstable motion, potentially
reducing flight speeds and increasing flight time and risk.

####  1.1.3 Payload Design

The container design, which houses the cargo being delivered by the vehicle,
requires special consideration to ensure secure attachment. While also
guaranteeing the safety of the payload and any entities that come in range of
the vehicle. This is crucial due to potential turbulence experienced during
flight that could displace the payload from the chassis or damage it while
inside the housing. Secure attachment of the payload is based on the type of
gripper used and any modifications to the payload design that aids this
gripper technique. Attachments can range from specific material properties
such as ferrous materials for magnetic grippers. Or puncture points for
ingressive grippers and specific geometric shapes that aid in higher force
exertion. The shape and position of the payload also affects the aerodynamics
of the vehicle, degrading flight efficiency. The payload will induce a drag
force on the vehicle if exposed to external elements. Furthermore, the payload
can also lead to a disruption in the lift force generated by the thrust
generating mechanism. Further aggravating known effects such as the ground
effect. Finally, expanding upon the SWAP constraints, a larger payload leads
to more volume being preoccupied. Therefore, leading to less capacity for
sensors and equipment.

###  1.2 Environment Constraints

Khosiawan and Nielsen classify different environment zones based on the
characteristics of each area [khosiawan_system_2016]. The ease of navigation
for each zone varies as there can be different hazards or weather conditions
that affect flying capabilities.

Table 2: Table illustrating different environment conditions a UAV could face in the context of package delivery. Landing / Takeoff conditions consist of stationary and dynamic platforms. While in transit, the UAV can either fly over high or low populated areas. Landing / Takeoff |  In Transit
---|---
Stationary delivery (target within a garden) |  Urban area (cities and towns)
Stationary re-package (storage facility, warehouse or depot) |  Low populated (woodland or farmland)
Moving re-package (truck for drone-truck collaborative operation) |

For this paper, we have found it helpful to categorise environments into
either landing/takeoff or transit. Then, further classify transit areas based
on population density and landing/takeoff based on the task of the vehicle.
Densely populated areas lead to higher concentrations of people and assets,
and therefore larger risk associated with the delivery compared to lower
populated areas. Alternatively, delivering and re-packaging are sub-tasks for
the unmanned aerial delivery vehicle to undertake. The location for delivery
may be within private property such as within the curtilage of a garden which
can have legal implications. Furthermore, dynamic obstacles, such as people or
pets, in unknown and potentially GPS-denied environments would require state-
of-the-art intelligent navigation algorithms. Re-packaging can be done either
at a warehouse or on a truck through drone truck collaborative operations.
Dynamic landing platforms, such as above a truck, require coordinated control
schemes to ensure stable landing which can be done through specialised landing
gears or perching.

###  1.3 Legal Constraints

Many regulatory bodies have been established to aid policymakers in creating
new laws for UAVs, specifically delivery UAVs. This includes the International
Civil Aviation111https://www.icao.int along with national organisations such
as the Civil Aviation Authority222https://www.caa.co.uk in the United Kingdom.
These organisations are appointed by governments to establish national or
international standards and to ensure consistent compliance. Stöcker et al
reviews current national and international regulations from around the globe
[stocker_review_2017]. They illustrate globally varying degrees of rigidity
and maturity. The following section aims to demystify the legislative
constraints on UAVs within the context of package delivery. Furthermore, the
parameters that affect these regulations are also discussed. This includes
operational limitations, privacy, security, safety, and environmental impact.

####  1.3.1 Operation Limitations

Operational regulations refer to the restrictions of physical flight. Due to
the novelty of autonomous flight, regulatory bodies are hesitant to introduce
rules for these types of vehicles. In contrast, the regulations governing
remotely piloted aircraft, which are better defined. This is not to be
confused with automatic operation, such as a pre-programmed instruction, where
the remote pilot can intervene. Autonomous navigation is still a new field,
and organizations are hesitant to provide guidance on regulations and
standards until a common understanding can be reached. Pilots must be able to
take control of the unmanned aircraft at any time, except when the data link
is
lost333https://www.easa.europa.eu/sites/default/files/dfu/AMC%20&%20GM%20to%20Part-
UAS%20%E2%80%94%20Issue%201.pdf. Some operations require permission, which
depends on the operation’s complexity [stocker_review_2017]. Furthermore,
pilots may take tests and practical training to show competency, with some
countries requiring pilot and UAV registration.

Flying Restrictions
Most countries have defined horizontal distances to points of interest and no-
fly zones [stocker_review_2017]. This includes safe reach away from people,
property and other vehicles, also known as self-separation. Examples include
airports and government buildings. Currently, UAVs present a severe risk and,
therefore, are not allowed to fly in controlled airspace or within the
proximity of people. Furthermore, some regulators prevent flights over
congested areas such as towns, cities and roads [stocker_review_2017]. In this
case, delivery UAVs would struggle to operate within urban areas and would
possibly require special flight corridors444https://news.sky.com/story/uks-
first-commercial-drone-corridor-to-open-in-reading-next-summer-12162260.

Current regulations aim to separate manned aircraft and UAVs, only allowing
UAV flights within a specific altitude [stocker_review_2017]. For example,
within the United States, the FAA defines the minimum safe altitude of 500
feet above the surface of non-congested areas like
cities555https://www.law.cornell.edu/cfr/text/14/91.119. Furthermore, the
legislation also requires emergency landing capability in case of power unit
failure to fly at any altitude. Also, flying over private property without
permission can lead to trespassing. In the case of an accident, the victim
could be compensated for personal injury or damage to property.

Flight restrictions also include the radial distance from the aircraft to the
pilot. There exist three ranges: visual line-of-sight (VLOS), extended visual
line-of-sight (EVLOS), and beyond visual line-of-sight (BVLOS)
[davies_review_2018]. Figure 3 visualises these three ranges. VLOS conditions
require the pilot to maintain unaided visual contact with the aircraft. In
contrast, BVLOS enables operations outside the visible range of the pilot.
Organisations and regulators are currently working towards updating policy to
enable BVLOS, with some predictions estimating BVLOS operation within the year
2035666https://www.sesarju.eu/sites/default/files/documents/reports/European%20ATM%20Master%20Plan%20Drone%20roadmap.pdf.
EVLOS provides remove pilots support from another deployed observer who can
maintain VLOS with the aircraft. Potential risks and issues can therefore be
communicated back to the remote
pilot777https://publicapps.caa.co.uk/docs/33/CAP%201861%20-%20BVLOS%20Fundamentals%20v2.pdf.

Figure 3: Illustrated ranges of visual line-of-sight, extended visual line-of-
sight, and beyond visual line-of-sight [davies_review_2018].

Package delivery is legally achievable through VLOS by employing a combined
drone-truck operation. Legislation must be flexible to enable package delivery
while protecting against trespassing. This would require accompanying
standardization to ensure public safety and positive opinion toward this
operation.

Technical Prerequisite
Pilots must consider technical requirements before a flight can commence. For
example, recently, the FAA has mandated all aircraft over 25 kg requires an
ADS-B out device888https://www.faa.gov/nextgen/equipadsb/. This device allows
the aircraft to broadcast its position, orientation and velocity to nearby
vehicles. However, additional sensors and components lead to less space and
further restrict the payload capacity.

####  1.3.2 Privacy

Research on privacy has been motivated by the advances in technology which
forces society to re-imagine what and where private space is
[nelson_view_2019]. Nelson et al. uses the definition of private space as an
area that is free from sensory interference or intrusion [nelson_view_2019].

Data from Sensors
According to Nelson’s definition, a person’s privacy is threatened due to the
UAV’s ability to manoeuvre freely within an environment without many
restrictions. Sensor data is required for state estimation, like visual
odometry and mapping algorithms to perform autonomous navigation. Hence,
capturing data of private property within the landing zone for package
delivery or unintentionally distinguishing objects can easily be done
[vannoy_commercial_2018]. Furthermore, more complicated algorithms can be used
to record and identify people through facial recognition and interpret
behaviours [mittal_deep_2020].

Governments have addressed this issue by updating regulations to protect
citizens’ privacy. In the UK, operators flying UAVs with cameras or listening
devices must follow the General Data Protection Regulation999https://register-
drones.caa.co.uk/drone-code/protecting-peoples-privacy. It is the
responsibility of the engineers to ensure protection measures are in place.
’Privacy-by-design’ must be incorporated to protect technically embedded data
[stocker_review_2017].

Lost Package
Another major privacy concern is the sensitive information placed on the
package along with the contents. Within a medical setting, customer-sensitive
information can be compromised if the UAV made the delivery to the wrong
location or if the payload was lost through malfunction or theft. The
correlation between a person’s name, address and prescription could enable
criminal activities such as identity theft. Lin et al. explains authentication
systems would ensure data protection in the event of a misplaced delivery
[lin_drone_2018].

Trust
The outlined privacy risks and safety issues have led to a negative perception
of UAVs. Winter et al. studied the emotional response of two types of police
missions involving UAVs in the United States [winter_mission-based_2016].
Their results showed citizen privacy concerns were more significant for
continuous operation within the police force. To the author’s knowledge, a
further study would be helpful to analyse the emotional response to continuous
commercial operations such as package delivery.

Researchers explain that the lack of trust in UAVs can be somewhat attributed
to a lack of knowledge and experience [nelson_view_2019]. Nelson and
colleagues study how an individual’s perception of privacy violation
correlates with the familiarity with UAVs. Their study shows that individuals
who have had exposure to UAVs understand the capabilities and regulations
surrounding these vehicles. They are somewhat less concerned with the growing
presence of UAVs regarding privacy than more naive citizens
[nelson_view_2019]. Therefore, the authors suggest that further improvements
in public education on the topic of UAVs would result in a significant
increase in public agreement.

####  1.3.3 Security

The two main methods of communication between UAVs and a ground station are
radio and WiFi [zhi_security_2020, yaacoub_security_2020]. These two
communication methods contain several vulnerabilities that can affect the
security of the UAV. These methods include Denial of Service (DOS), De-
authentication, Man in the Middle, Unauthorised root access, and package
spoofing [westerlund_drone_2019].

Sensor Spoofing
A spoofer can attempt to manipulate the navigation system of the UAV by
spoofing GPS signal. For this to happen, however, the spoofer needs to know
the UAV’s position, guidance system and target location. Along with the status
and internal signal processing method of the receiver installed
[seo_effect_2015]. The spoofed GPS signals need to radiate in the direction of
the UAV with a signal strength similar to a genuine GPS signal. In reality, it
is challenging to know all this information without having access to the
system. Alternatively, other sensors like a visual odometry system have flaws.
For example, optical flow spoofing has been shown to be effective in areas
where there are fewer surface features [davidson_controlling_2016].

Radio Frequency Spectrum Attacks - Denial of Service and Manipulation
Kulp and Mei identify types of cyber-attacks against delivery UAVs which would
aid in designing an attack detection system [kulp_framework_2020]. They show a
range vector can be used to maliciously manipulate the navigation system of
the UAV with hostile intent. DOS attacks prevent a user from accessing a
machine or network by flooding the target with traffic. Researchers have
investigated the impact of these attacks by sending requests to the UAV over
the network [hooper_securing_2016]. DOS attacks have been found to influence
the performance of the UAV negatively. Including a decrease in sensor
functionality, drops in telemetry feedback and reduced response to remote
control commands [vasconcelos_evaluation_2019]. If the data link is
unencrypted, a malicious actor could take control and perform different
control commands [hooper_securing_2016]. Alternatively, the hacker could
predict the frequency-hopping spread spectrum pattern by reverse-engineering
the transmitter or receiver. With delivery systems, malicious actors may be
interested in the theft of packages or disruption of service
[kulp_framework_2020]. Hardware used for detecting these threats increases the
weight and complexity of the UAV. Hence, the security benefit must exceed
these disadvantages.

####  1.3.4 Safety

The number of UAVs entering the airspace is increasing, which has raised
concerns regarding the risks to current manned aircraft. Human factors, sense
and avoid techniques, and redundancy techniques can improve the safety of
other members within the airspace and members of the public. Furthermore,
these risks impact insurance policies, standard operating procedures, and the
delivery UAV design.

Human Factors
Human factors play a significant role in the safety of UAVs. Multiple
practices and standards aid in reducing the risk associated with human factors
which includes crew resource management, standard operating procedures, and
safety management systems [weldon_use_2021]. These procedures are standard
within the aviation industry, but more literature is required to understand
how these standards can be applied to delivery UAVs. Regulation regarding
safety is based on proportional and operation-centric approaches
[stocker_review_2017]. This approach entails focusing on the contents and
conditions of the operation rather than just the characteristics of the UAV,
which provides more flexible regulation. Hierarchical and more strenuous pilot
testing for riskier tasks can further eliminate human errors. Further training
may be required when operating a delivery UAV, which includes operating the
aerial manipulator or how to safely protect the payload and UAV during a
fault.

Collision Avoidance
Equivalent collision avoidance capabilities to current manned aircraft are
required to integrate UAVs into the national airspace safely [yu_sense_2015].
Typically, pilots rely on ’see-and-avoid’ while utilizing other detect and
avoid techniques. These techniques include ground-based infrastructure,
electronic identification, onboard detect and avoid equipment, and traffic
management software. For VLOS operation, the pilot has environmental
knowledge. However, for BVLOS the operator only receives sensory information
from the onboard sensors. Sensory information is limited as the limited field-
of-view camera images and other sensors provide a partially observable
understanding of the environment. Furthermore, sensory cues lose critical
information like sound, kinaesthetic and an ambient view [yu_sense_2015]. A
certificate of airworthiness may be required to fly the aircraft. This
certificate ensures the aircraft conforms to its manufacturing design and
provides a further regulatory barrier for unsafe equipment. Difficulties in
obtaining this certificate may be due to unconventional designs such as an
aerial manipulator system in delivery UAVs.

Hazards
Typical safety hazards may include control issues from transmission loss,
collisions, partial or complete failure of navigation systems or components or
structural integrity, severe weather or climatic events, and take-off and
landing. In the context of delivery UAVs, hazards can be specifically
identified. However, there is a lack of literature pertaining to the
identification of safety hazards and risk management for delivery UAVs. In
general, additional risks include dropping the payload, take-off and landing
on private property, aerial manipulation and ensuring separation between a
citizen or personal belongings and the manipulators’ configuration space.

Insurance
The availability of commercial insurance is essential for risk management and
to aid in commercialization. Insurance involves understanding all the
parameters that influence risk. Risks include the legality, operational use,
training and experience or the list of human factors, system reliability and
system value. Specifically for delivery UAVs, this can include payload
characteristics, aerial manipulation design and landing methodology
(especially for drone truck collaboration). Insurance provides a clear
advantage of indicating a regime that sufficiently compensates for harm or
damage caused by the flight operation [stocker_review_2017]. Rapidly evolving
technology within the field is leading to difficulty for insurance companies.
Hence, as mentioned in this section, these companies will need to embrace the
constantly changing policies along with rapid changes to design, environmental
and social-political constraints.

####  1.3.5 Environmental Impact

Delivery UAVs can impact the environment through noise and disruption to
wildlife.

Noise Pollution
Noise emission through delivery manoeuvres close to citizens in urban areas or
flight corridors is an emerging problem. Research suggests noise from
propellers can be considerably more irritating than road traffic or passenger
aircraft noise [schaffer_drone_2021, christian_initial_2017]. This noise is
caused by pure tones and high-frequency broadband sounds. Using psychoacoustic
testing, researchers can quantify the irritation level and impact of UAV noise
pollution. Further research compared psychoacoustic indices of stimuli from
different types of aircraft. The research from Torija et al. showed quadrotors
caused the highest irritation than other aircraft and road vehicles
[torija_psychoacoustic_2019]. The authors found that the most significant
factor of this result was the quadcopter’s higher loudness, sharpness and
tonality. Finally, Gwak et al. analysed the annoyance level with respect to
the size of the UAV [gwak_sound_2020]. They found that larger drones lead to
higher annoyance levels due to variations in tonal characteristics, sharpness
and fluctuational in strength of the sound.

The most dominant source of noise is the propulsion system which can include a
combination of engine or motor and propeller [miljkovic_methods_2018]. Noise
generated from the airframe is considered to be negligible at lower speeds in
comparison to other sources of noise. Therefore, fixed-wing-based UAVs appear
to be the quietest compared to other thrust-generating designs. Hybrid-based
designs, like the VTOL, gain this advantage while also being able to land
vertically, allowing for more precise package delivery compared to fixed-wing
designs. Alternatively, researchers have investigated passive and active
methods to reduce UAV noise [miljkovic_methods_2018]. These methods include
modifying the blade shape, absorbing and reflective barriers, ductive
propellers and active noise control. Active methods, such as active noise
control, require additional power which contributes to the SWAP constraints
but tends to be better at cancelling noise.

Aesthetic Impact
Similar to the irritation of noise, the increased use of airspace could lead
to further resistance against the inclusion of delivery UAVs
[nentwich_vision_2018]. Furthermore, impact with the environment such as bird
migration would cause disruption to natural habitats [gray_pilot_2021]. Risks
like these could be solved via global routing problems and flight corridors.


# On the number of fixed points of the map $\gamma$

Niccolò Castronuovo
Dipartimento di Matematica, Università di Bologna, Bologna, 40126, ITALY

###### Abstract

We recursively define a sequence $\\{F_{n,k}\\}_{n,k\in\mathbb{N}}$ and we
prove that such sequence contains only the symbols $\\{0,1\\}.$ We investigate
some number-theoretic properties of such sequence and of the way it can be
generated. The number $F_{n}$ can be interpreted as the number of fixed points
of semilength $n$ of the map $\gamma$ introduced in [2]. Our results partially
answers conjectures posed in [4].

##  1 Introduction

In this paper we consider an infinite $(0,1)$-matrix $F$ defined in the
following way. Let $F:=[F_{n,k}]_{n\geq 0\,k\geq 0}$ be the doubly-infinite
matrix all of whose entries are equal to $0.$ Apply to $F$ the following step:

  * Step 0

Set $F_{0,0}=1.$

For all $i\geq 1$ apply to $F$ the following step:

  * Step $i$

For each pair $(n,k)$ such that the entry $F_{n,k}$ changes its value in Step
$i-1,$ increase $F_{n+k,k}$ and $F_{3n+1-2k,2n+1-k}$ by $1.$

$F$ is the matrix obtained in this way.

We say that an entry $F_{n,k}$ of matrix $F$ is created at Step $i$ if
$F_{n,k}>0$ and, during the creation of matrix $F$ it changes its value during
Step $i.$

It is trivial to verify that $F_{0,k}>0$ if and only if $k=0$ and that
$F_{n,k}=0$ if $k>n.$ Hence the matrix $F$ is lower triangular and
$\\{F_{n,k}\\}_{n\geq 0\,k\geq 0}$ can be thought as a doubly-indexed
sequence.

The matrix $F$ is related to the map $\gamma,$ a bijection defined over the
set of Dyck words of semilength $n.$ This map and its properties are
introduced in [2] and further studied in [3] and [4]. This last paper, in
particular, deals with the characterization of the fixed points of $\gamma.$

More precisely, $F_{n,k}$ is equal to the number of Dyck words of semilength
$n,$ with principal prefix of length $k$ and fixed under the action of
$\gamma.$ The fact that there is at most one of such words (see [2]) implies
that the matrix $F$ is a $0-1$ matrix. We will reprove this result in
Corollary 2.3. The sum of entries in row $n,$ $F_{n}:=\sum_{k}F_{n,k},$ is the
total number of Dyck words of semilength $n$ fixed by $\gamma$ (see [2] for
the main definitions).

The reason for which we do not reintroduce the definition of the map $\gamma$
is that the sequence $\\{F_{n,k}\\}_{n,k}$ can be defined implicitly as above
(see [4]). Hence all the results of the paper can be stated in a number-
theoretic form without appealing to the original definition of $F_{n}.$

The first few rows of the matrix are reported below (the elements above the
main diagonal are all zeros and are not indicated).

$F=\setcounter{MaxMatrixCols}{18}\begin{matrix}1&&&&&&&&&&&&&&&&&\\\
0&1&&&&&&&&&&&&&&&&\\\ 0&1&1&&&&&&&&&&&&&&&\\\ 0&1&0&1&&&&&&&&&&&&&&\\\
0&1&1&0&1&&&&&&&&&&&&&\\\ 0&1&0&0&1&1&&&&&&&&&&&&\\\
0&1&1&1&0&0&1&&&&&&&&&&&\\\ 0&1&0&0&0&0&0&1&&&&&&&&&&\\\
0&1&1&0&1&0&1&1&1&&&&&&&&&\\\ 0&1&0&1&1&0&0&1&0&1&&&&&&&&\\\
0&1&1&0&0&1&0&0&0&0&1&&&&&&&\\\ 0&1&0&0&0&0&0&0&1&0&1&1&&&&&&\\\
0&1&1&1&1&0&1&0&0&0&0&0&1&&&&&\\\ 0&1&0&0&1&0&0&0&0&0&1&1&0&1&&&&\\\
0&1&1&0&0&0&1&1&0&0&1&0&1&1&1&&&\\\ 0&1&0&1&0&1&0&1&0&0&0&1&0&0&0&1&&\\\
0&1&1&0&1&0&0&1&1&0&0&0&0&0&0&0&1&\\\ 0&1&0&0&1&0&0&0&0&0&0&0&1&1&0&0&1&1\\\
&\dots\end{matrix}$

The first values of the sequence $\\{F_{n}\\}_{n\geq 0}$ are

$1,1,2,2,3,3,4,2,6,5,4,4,6,5,8,6,6,6\ldots$

We study the matrix $F$ and the sequence $F_{n},$ and investigate their
properties.

Our results partially answer the following two conjectures posed to the author
by Cori [4].

######  Conjecture 1.1.

$F_{n}\geq 3$ for all $n>7.$

######  Conjecture 1.2.

$\lim_{n\to\infty}F_{n}=\infty.$

In particular we answer in the affirmative Conjecture 1.1 and give some
results toward the solution to Conjecture 1.2.

##  2 The matrix $F$ and a free subsemigroup of $SL(3,\mathbb{Z}).$

Identify the entry $F_{i,j}$ of the matrix $F$ with the integer vector with
coordinates $(i,j)$ in the $\mathbb{Z}\times\mathbb{Z}$ lattice plane. It
follows immediately from the definition of the matrix $F,$ that, if $i,j>1,$
$F_{i,j}>0$ if and only if the vector $(i,j)$ can be reached iteratively
applying to the vector $(1,1)$ the following affine transformations (in
arbitrary order)

$\hat{G}:\begin{pmatrix}x\\\ y\end{pmatrix}\to\begin{pmatrix}1&1\\\
0&1\end{pmatrix}\cdot\begin{pmatrix}x\\\ y\end{pmatrix},$

and

$\hat{S}:\begin{pmatrix}x\\\ y\end{pmatrix}\to\begin{pmatrix}3&-2\\\
2&-1\end{pmatrix}\cdot\begin{pmatrix}x\\\ y\end{pmatrix}+\begin{pmatrix}1\\\
1\end{pmatrix}.$

The group generated by the affine transformations $\hat{G}$ and $\hat{S}$ can
be identified with the subgroup $\langle S,G\rangle$ of $SL(3,\mathbb{Z})$
generated by matrices

$G=\begin{pmatrix}1&1&0\\\ 0&1&0\\\ 0&0&1\end{pmatrix}\quad\mbox{ and }\quad
S=\begin{pmatrix}3&-2&1\\\ 2&-1&1\\\ 0&0&1\end{pmatrix}.$

In this identification, the actions of $\hat{S}$ and $\hat{G}$ on the lattice
point $(x,y)\in\mathbb{Z}^{2}$ correspond to the actions of $S$ and $G,$
respectively, on the lattice point $(x,y,1)\in\mathbb{Z}^{3}.$ Hence we can
consider directly the action of the group $<S,G>$ over the set
$\mathbb{Z}^{2}.$ If $w\in<S,G>,$ we denote by $w(x,y)$ the image of the
vector $(x,y)$ under this action.

Now we study some properties of the group $<S,G>$ and of matrices $S$ and $G.$

Notice that the group generated by $S$ and $G$ is not free. In fact we have
$(GS^{-1})^{4}=\begin{pmatrix}1&0&0\\\ 0&1&0\\\ 0&0&1\end{pmatrix}.$ If we
restrict our attention to the monoid generated by $S$ and $G,$ it is free.

######  Theorem 2.1.

The monoid $H$ generated by $S$ and $G$ is free. The action of $H$ on
$\mathbb{Z}^{2}$ is free i.e. for all $(x,y)\in\mathbb{Z}^{2}$ if
$w(x,y)=w^{\prime}(x,y),$ with $w,w^{\prime}\in H,$ then $w=w^{\prime}.$

For the proof it will be useful a version of the so called Ping-Pong lemma or
Table-Tennis lemma for semigroups (see e.g. [5][p. 188]), that we report here.

######  Lemma 2.2.

Let $\Gamma$ be a group acting on a set $X.$ Assume that there exist
$\gamma_{1},\gamma_{2}\in\Gamma$ and $X_{1},X_{2}\subseteq X$ such that
$X_{1}\cap X_{2}=\emptyset,$ $\gamma_{1}(X_{1}\cup X_{2})\subseteq X_{1}$ and
$\gamma_{2}(X_{1}\cup X_{2})\subseteq X_{2}.$ Then the semigroup generated in
$\Gamma$ by $\gamma_{1}$ and $\gamma_{2}$ is free.

Now we proceed to the proof of Theorem 2.1.

###### Proof.

For the first part, we apply the previous lemma with $\gamma_{1}:=G,$
$\gamma_{2}:=S$ and $\Gamma:=H.$ As described above, $H$ acts in the standard
way on the set $X=\mathbb{Z}^{2},$ and, more generally, on $\mathbb{R}^{2}.$
Notice that the only fixed point under the action of $H$ on $\mathbb{R}^{2}$
is $(-0.5,0),$ hence any line through this point is mapped onto another such
line. Moreover, every point of the line $y=x+\frac{1}{2}$ is fixed by $S$ and
every point of the line $y=0$ is fixed by $G.$

We consider the following disjoint subsets of $X:$

$X_{1}:=\\{(x,y)\in\mathbb{Z}^{2}\,|\,x>-\frac{1}{2}\,,\,0<y<\frac{x}{2}+\frac{1}{4}\\}$
$X_{2}:=\\{(x,y)\,|\,x>-\frac{1}{2}\,,\,\frac{2x}{3}+\frac{1}{3}<y<x+\frac{1}{2}\\}$

Those subsets are depicted in the figure below.

$X_{1}$$X_{2}$

It is trivial to verify that

$G(X_{1}\cup X_{2})\subseteq X_{1},\quad\quad S(X_{1}\cup X_{2})\subseteq
X_{2}.$

Now we prove the second part of the theorem. We want to show that

$\forall(x,y)\in\mathbb{Z}^{2},\quad\mbox{ if }w(x,y)=w^{\prime}(x,y),\mbox{
with }w,w^{\prime}\in H,\,\mbox{ then }w=w^{\prime}.$

We proceed by induction on the minimum of the lengths of $w$ and $w^{\prime},$
thought as words in the letters $S$ and $G,$

$m:=\min\\{|w|,|w^{\prime}|\\}.$

If $m=0$ then one of the two words is the identity. The equation
$w(x,y)=(x,y),$ with $w$ different from the identity is clearly impossible
since both $S$ and $G$ increase the abscissa of the point on which they act.
Suppose the assertion true for all values of $m$ up to $N.$ If $m=N+1$ and the
first letter of $w$ and $w^{\prime}$ is the same, e.g. the letter $G,$ we have
$w=G\hat{w},$ $w^{\prime}=G\hat{w}^{\prime}$ and
$G\hat{w}(x,y)=G\hat{w}^{\prime}(x,y).$ This implies
$\hat{w}(x,y)=\hat{w}^{\prime}(x,y)$ and hence $w=w^{\prime}$ by the inductive
hypothesis. If $m>0$ and $w=G\hat{w}$ and $w^{\prime}=S\hat{w^{\prime}},$ then
$w(x,y)\in X_{1}$ and $w^{\prime}(x,y)\in X_{2}.$ Since $X_{1}\cap
X_{2}=\emptyset$ it is impossible that $w(x,y)=w^{\prime}(x,y).$

This concludes the proof. ∎

As recalled above, there is a bijection between $H$ and the set
$\\{(i,j)|\,i,j>0,\,F_{i,j}\neq 0\\}.$ This bijection maps an element $w\in H$
to the pair $w(1,1).$ Hence the previous theorem leads to the following
corollary.

######  Corollary 2.3.

The matrix $F$ is a 0-1 matrix.

The following lemma will be useful in the sequel.

######  Lemma 2.4.

The matrices $S$ and $G$ satisfy the following identities for all $i$

$G^{i}=\begin{pmatrix}1&i&0\\\ 0&1&0\\\ 0&0&1\end{pmatrix},$
$S^{i}=\begin{pmatrix}2i+1&-2i&i\\\ 2i&-(2i-1)&i\\\ 0&0&1\end{pmatrix},$
$S^{i}G=\begin{pmatrix}2i+1&1&i\\\ 2i&1&i\\\ 0&0&1\end{pmatrix},$
$(SG)^{i}=\begin{pmatrix}a(i)&b(i)&c(i)\\\ d(i)&a(i-1)&b(i)\\\
0&0&1\end{pmatrix}$

where

  * •

$a(n)$ satisfies $a(n)=4a(n-1)-a(n-2)$ with $a(0)=1$ and $a(1)=3$ (it is, up
to a shift, sequence A001835 in [7]).

  * •

$b(n)$ satisfies $b(n)=4b(n-1)-b(n-2)$ with $b(0)=0$ and $b(1)=1$ (it is
sequence A001353 in [7]).

  * •

$c(n)$ satisfies $c(n)=5c(n-1)-5b(n-2)+c(n-3)$ with $c(1)=1$ and $c(k)=0$ for
$k\leq 0$ (it is sequence A061278 in [7]).

  * •

$d(n)$ satisfies $d(n)=4d(n-1)-d(n-2)$ with $d(0)=0$ and $d(1)=2$ (it is
sequence A052530 in [7]).

###### Proof.

The assertions are easily provable by induction. ∎

Now consider the subset of $\mathbb{Z}\times\mathbb{Z}$ whose points have
equal positive coordinates

$A=\\{(k,k)\,|\,k\in\mathbb{Z}\,k\geq 0\\}.$

Clearly

$A=\cup_{i\geq 0}\\{S^{i}(1,1)\\}\cup\\{(0,0)\\}.$

Hence,

$F_{k,k}=1$

if $k\geq 0.$ Moreover, by the previous lemma,

$\cup_{i\geq 0}G^{i}(A)=\\{(kd,d)\,|\,k,d\in\mathbb{N}\,,k>0\\}.$

This implies the following proposition.

######  Proposition 2.5.

If $n\geq 1$ and $k$ divides $n$ then $F_{n,k}=1.$

The previous proposition implies that

$F_{n}\geq\tau(n),$

where $\tau$ is the number-of-divisors function (see e.g. [1]). We will see
below that the previous inequality can be substantially improved.

##  3 A modular recursion

Now we prove a lemma that show how the entries of the matrix $F$ are related
to each others through a modular recursion of the indices.

######  Lemma 3.1.

Consider the matrix $F.$ Then

$F_{n,k}=F_{n-k,h},$ (1)

where $h$ is the remainder of $2n-2k+1$ in the division by $k,$ i.e.

$h\equiv k\mod{2n-2k+1}$

and $0\leq h\leq 2n-2k.$ Equation (1) together with the initial condition
$F_{0,0}=1$ characterizes the matrix $F.$

###### Proof.

As recalled above, if $F_{n,k}=1$ then $1\leq k\leq n$ or $k=n=0.$ The lemma
is clearly true for the entries of the form $F_{n,n},$ $n\geq 0,$ i.e. those
obtained applying only the operation $S$ to $(1,1).$ In fact, in this case,
$F_{n,n}=1,$ $h=0,$ $n-k=0$ and $F_{0,0}=1.$

Now choose a pair $(n,k)$ with $k<n.$ We want to show that
$(n,k)=S^{i}G(n-k,h),$ $i\geq 0.$ By Lemma 2.4, $(n,k)=S^{i}G(x,y)$ if and
only if $n=(2i+1)x+y+i$ and $k=2ix+y+i.$ Hence $n-k=x,$ $2n-2k+1=2x+1$ and
$h=y.$

Note that $F_{n,k}=1$ with $k<n$ if and only if $(n,k)=w(1,1)$ where $w\in H$
is a non-empty word with at least one letter equal to $G.$ Let
$w=S^{i_{l}}GS^{i_{l-1}}G\ldots S^{i_{1}}GS^{i_{0}},$ where $l_{j}\geq 0$ for
all $0\leq j\leq l.$ Set

$(x,y):=S^{i_{l-1}}G\ldots S^{i_{1}}GS^{i_{0}}(1,1).$

Then $(n,k)=S^{i_{l}}G(x,y).$ Thus $F_{n,k}=F_{x,y}.$ ∎

##  4 The number-of-divisors function and the matrix $F$

######  Theorem 4.1.

For every $n\geq 1$ and for every $x$ such that

  * •

$0\leq x\leq n-1$ and

  * •

there exists a divisor $h$ of $x$ with $2x+1\,|\,2n-2h+1,$

it holds $F_{n,n-x}=1.$

###### Proof.

If $x=0$ the proposition is trivial. Let $x\geq 1$ be an integer. Then, by
Lemma 3.1, we have $F_{n,n-x}=F_{x,h}$ where $h\equiv n-x\mod{2x+1}.$ Now, by
Proposition 2.5, we have that $F_{x,h}=1$ if $h\,|\,x.$ Moreover $h\equiv
n-x\mod{2x+1}$ if and only if $2x+1\,|\,n-x-h.$ Since $2x+1$ is odd this last
condition is equivalent to $2x+1\,|\,2n-2x-2h$ and this in turn is equivalent
to $2x+1\,|\,2n-2h+1.$ Hence, if $h|x$ and $2x+1\,|\,2n-2h+1,$ we have
$F_{n,n-x}=1.$ ∎

We denote by $a_{n}$ the number of entries $F_{n,n-x}$ of row $n$ of the
matrix $F$ such that $0\leq x\leq n-1$ and there exists a divisor $h$ of $x$
with $2x+1|2n-2h+1.$ Clearly

$a_{n}\leq F_{n},$

for every $n.$

######  Theorem 4.2.

We have

$a_{n}\geq\max\\{\tau(n),\,\tau(2n-1),\,\tau_{o}(n+1)\\},$

more precisely

$a_{n}\geq\tau(n)+\tau(2n-1)+\tau_{o}(n+1)-3-\delta_{n\equiv 0\mod
2}-\delta_{n\equiv-1\mod 3}$

for every $n\geq 1,$ where $\tau$ is the number-of-divisors function and
$\tau_{o}$ is the number-of-odd-divisors function.

###### Proof.

Let $n-x$ be a divisor of $n.$ Then $n=(n-x)j,$ where $j$ is an integer. Then
$2x+1=2n-2\frac{n}{j}+1.$ Since $\frac{n}{j}=n-x$ is a divisor of $n,$ it
divides also $x,$ hence $F_{n,n-x}$ is one of those entries counted by
$a_{n}.$ Hence $a_{n}\geq\tau(n).$ Notice that, in this case, $x=0$ or
$n-x\leq\frac{n}{2}.$

From the previous theorem, taking $h=1,$ it follows, in particular, that
$F_{n,n-x}=1$ if $2x+1$ is a divisor of $2n-1.$ Hence $a_{n}\geq\tau(2n-1)$
and $x=n-1$ or $2x+1\leq\frac{2n-1}{2}.$ In the last case,
$x\leq\frac{n-1}{2}$ and $n-x\geq\frac{n+1}{2}.$ As a consequence
$a_{n}\geq\tau(n)+\tau(2n-1)-2,$ where the 2 in the right-hand side takes into
account the fact that $F_{n,n}$ and $F_{n,1}$ have been counted two times.

Similarly, taking $h=x$ in the previous theorem, it follows that $F_{n,n-x}=1$
when $x$ is such that $2x+1\,|\,2n-2x+1.$ This is equivalent to
$2x+1\,|\,2n+2$ which, since $2x+1$ is odd, is in turn equivalent to
$2x+1\,|\,n+1.$ Hence $F_{n,n-x}=1$ if $2x+1$ is an odd divisor of $n+1$ and
$a_{n}\geq\tau_{o}(n+1).$ Here $x=\frac{n}{2}$ or $2x+1\leq\frac{n+1}{2}.$ In
the last case $x\leq\frac{n-1}{4}$ and $n-x\geq\frac{3n+1}{4}.$

Notice that if $2x+1$ divides $n+1$ and $2n-1$ it divides also
$2(n+1)-(2n-1)=3$ hence $x=0$ or $x=1.$ If $x=1,$ $2x+1=3$ divides $n+1$ if
and only if it divides also $2n-1.$

Hence

$a_{n}\geq\tau(n)+\tau(2n-1)+\tau_{o}(n+1)-3-\delta_{n\equiv 0\mod
2}-\delta_{n\equiv-1\mod 3}$

where, in the right hand side, the 3 takes into account the fact that
$F_{n,n}$ has been counted three times and $F_{n,1}$ has been counted two
times, the $\delta_{n\equiv 0\mod 2}$ takes into account the fact that
$F_{n,\frac{n}{2}}$ has been counted two times if $n$ is even and
$\delta_{n\equiv-1\mod 3}$ takes into account the fact that $F_{n,n-1}$ has
been counted two times if $n+1$ is divisible by 3. ∎

Since a number has 1 as its only odd divisor if and only if it is a power of
2, the previous theorem shows that Conjecture 1.1 is proved for every $n>7$
except those primes $p$ of the form $p=2^{q}-1$ such that $2p-1$ is also
prime. Notice that the fact that $F_{n}\geq 3$ for every $n\neq 2^{q}-1$
follows also from Remark 1 in [4].

A prime $p$ of the form $2^{q}-1$ is said to be a Mersenne prime (see e.g.
[1]). The Mersenne primes $p$ such that $2p-1$ is also prime appears in [7] in
sequence A167917. It is well known that, if a prime $p$ has the form
$2^{q}-1,$ then also $q$ is prime.

######  Theorem 4.3.

The number $a_{n}$ is one plus the number of solutions of the Diophantine
equation

$n=2xyz+yz+x+y,\quad\mbox{ with }\,y,z\geq 1\,\mbox{ and }\,x\geq 0.$ (2)

Moreover,

$a_{n}=1+\sum_{0\leq j<n}D_{2j+1}(n-j),$

where $D_{m}(n)$ is the number of divisors $d>1$ of $n$ congruent to 1 $\mod
m.$

###### Proof.

Let $n$ be fixed. The number of elements of the form $F_{n,n-x}$ with $x\neq
0,$ such that there exists an $h$ with $h|x$ and $2x+1|2n-2h+1$ is equal to
the number of solutions $h,k,j\geq 1$ to the equation

$2n-2h+1=j(2hk+1)$ (3)

i.e.

$2n=2jhk+2h+j-1.$

In this equation $j$ must be odd and hence $j=2\hat{j}+1.$ So we get the
equation

$n=2\hat{j}hk+hk+h+\hat{j},\quad\mbox{ with }\,h,k\geq 1\,\mbox{ and
}\,\hat{j}\geq 0.$ (4)

Hence $a_{n}$ is equal to the number of solutions to this equation increased
by one since we have to take into account the case with $x=0.$

Consider now Equation 4. It is equivalent to

$n-\hat{j}=h((2\hat{j}+1)k+1).$

Hence, if $n$ and $\hat{j}\geq 0$ are fixed, there is a correspondence between
the solutions $h,k\geq 1$ to the last equation and the number of divisors
$d=(2\hat{j}+1)k+1>1$ of $n-\hat{j}$ congruent to one $\mod 2\hat{j}+1.$ ∎

Now we prove Conjecture 1.1.

######  Theorem 4.4.

$F_{n}\geq 3$ for all $n>7.$

###### Proof.

As recalled above, the assertion follows from the previous results for every
$n>7$ except those primes $p$ of the form $p=2^{q}-1,$ $q$ a prime, such that
$2p-1$ is also prime.

Let $p$ be a number with these properties such that $F_{p}=2.$ Since
$F_{n}\geq a_{n}$ for every $n$ and since $a_{n}\geq 2$ by Theorem 4.2, we
have $a_{p}=2.$ Moreover

$a_{p}\geq 1+D_{1}(p)+D_{3}(p-1).$

Clearly $D_{1}(p)=1.$ Hence $D_{3}(p-1)=0.$ We want to show that it is
impossible. The integer $p-1$ has no divisors $d>1$ such that $d\equiv
1\mod{3}$ if and only if $p-1=3^{r}p_{1}^{i}$ where $p_{1}$ is a prime with
$p_{1}\equiv-1\mod{3},$ $i=0$ or $i=1$ and $r\geq 0.$ In fact, if between the
prime factors of $p-1$ there were more than one congruent to $-1$ $\mod{3}$ or
at least one congruent to $1$ $\mod{3},$ then $p-1$ would have at least one
divisor congruent to $1$ $\mod{3}.$

Since $p=2^{q}-1,$ we have

$2(2^{q-1}-1)=3^{r}p_{1}^{i}$

which implies $p_{1}=2,$ $i=1$ and $2^{q-1}-3^{r}=1.$ The only solutions to
the previous equation in positive integers $q$ and $r$ are $q=3$ and $r=1.$ In
fact, in $2002,$ Mihăilescu proved that the only solution to the Diophantine
equation $x^{a}-y^{b}=1,$ with $x,y,a,b>1$ is $x=3,$,$y=2,$ $a=2,$ $b=3,$ thus
solving the celebrated Catalan’s conjecture (see [6], the solution of the
particular case of this conjecture with $x=2$ and $y=3$ is attributed to
Gersonides).

If $q=3$ and $r=1,$ we get $p=7,$ whereas we are considering a number $p>7.$
This concludes the proof.

∎

##  5 Other properties of the matrix $F$

In this section we investigate further properties of matrix $F.$

######  Theorem 5.1.

Matrix $F$ has periodic diagonals. In particular, the $a$-th subdiagonal has
period $2a+1.$

Matrix $F$ has periodic columns. In particular, column $a$ has period $a$.

###### Proof.

To prove the first part of the theorem, fix $a\in\mathbb{N}$ and consider the
elements $F_{n,n-a},$ $n>a,$ of the matrix $F.$ These elements constitute the
$a$-th subdiagonal. By Lemma 3.1 we have $F_{n,n-a}=1$ if and only if
$F_{a,h}$ where $h\equiv n-a\mod{2a+1}.$ Since $a$ is fixed, this proves that
the $a$-th subdiagonal is periodic with period $2a+1.$

To prove the second part, fix $a\in\mathbb{N}$ and consider the elements
$F_{n,a},$ $n\geq a.$ These elements constitutes the $a$-th column of $F.$ By
Lemma 3.1 $F_{n,a}=1$ if and only if $F_{n-a,h}$ where $h\equiv
a\mod{2n-2a+1}.$ If $n$ is sufficiently large, this implies $h=a$ and hence
the $a$-th column has period $a.$ ∎

######  Theorem 5.2.

For each quadruple $(k,d,i,j)\in\mathbb{N}^{4},\,k>0,$ we have

$F_{kd+id+j(i+1)(2(k-1)d+1),d+j(2(k-1)d+1)}=1.$

###### Proof.

Consider the set $A:=\\{(kd,d)\,|\,k,d\in\mathbb{N}\,,k>0\\}.$ We have
$F_{x,y}=1$ for all $(x,y)\in A$ by Proposition 2.5. By Lemma 3.1, we have

$\cup_{i,j\geq 0}G^{i}S^{j}(A)=$
$\\{kd+id+j(i+1)(2(k-1)d+1),d+j(2(k-1)d+1))\,|\,k,d,j,l\in\mathbb{N}\,,k>0\\}.$

This concludes the proof. ∎

The previous theorem implies the following Corollary.

######  Corollary 5.3.

For each $t\in\mathbb{N},$ $F_{3t+2,2t+2}=1$ and $F_{5t+4,2t+2}=1.$

###### Proof.

For the first part, substitute $i=0,d=1,j=1$ and $k-1=t$ in the previous
theorem. For the second part, by Lemma 3.1, we get $F_{5j+4,2j+2}=1$ if and
only if $F_{3j+2,h}=1$ where $h\equiv 2j+2\mod{6j+4}$ i.e. $h=2j+2.$ Since
$F_{3j+2,2j+2}=1$ by the first part, we get the assertion. ∎

##  6 Conjectures about the matrix $F$

In this section we formulate others conjectures about $F$ and explain their
relation with Conjecture 1.1. To this aim we need to introduce the notion of
track vector.

Denote by $\phi$ the map that associates the pair of integers $(n,k)$ the pair
$(n-k,h)$ where $h\equiv k\mod 2n-2k+1$ and $0\leq h\leq 2n-2k.$ It follows
from the proof of Lemma 3.1 that $\phi(n,k)=(n-k,h)$ if and only if there
exists an $i\in\mathbb{N}$ such that $S^{i}G(n-k,h)=(n,k).$ As a consequence,
$(n,k)=S^{i_{l}}GS^{i_{l-1}}G\ldots S^{i_{1}}G(m,m),$ where
$i_{1},\ldots,i_{l},m\in\mathbb{N},$ if and only if $\phi^{i_{l}}(n,k)=(m,m).$

The number of operations of the form $S^{i}G$ needed to get a given element is
related to the breadth of an element. Here we recall the definition of breadth
and of track vector. Following [4], thetrack vector of an element $(n,k)$ is
defined as the vector $(i_{0}+1,\ldots,i_{l}+1)$ where

$(n,k)=S^{i_{l}}GS^{i_{l-1}}G\ldots S^{i_{1}}GS^{i_{0}}(1,1).$

In this case, the breadth of $(n,k)$ is equal to $l.$ Since
$S^{i_{0}}(1,1)=(i_{0},i_{0}),$ the breadth of $(n,k)$ is equal to the number
of times it is necessary to apply the map $\phi$ to $(n,k)$ to get an entry of
the form $(m,m).$

######  Theorem 6.1.

The elements of $F$ appearing in Theorem 4.1 with $x\neq 0,$ i.e. the elements
$F_{n,n-x},$ $x\neq 0,$ such that there exists an $h$ with $h|x$ and
$2x+1|2n-2x+1$ are precisely the elements in row $n$ with track vector of the
form $(a,(1)^{p},b),$ with $a,b,p\geq 1.$

Moreover, if $n$ is fixed, the number of elements $F_{n,n-x},$ $x\neq 0,$ such
that there exists an $h$ with $h|x$ and $2x+1|2n-2x+1$ is equal to the number
of elements in row $n$ with track vector $((1)^{p},a,(1)^{q}),$ where $p,q\geq
0,$ $a\geq 2.$

###### Proof.

By the previous observations and by the proof of Theorem 4.1, we have that the
elements $F_{n,n-x},$ $x\neq 0,$ such that there exists an $h$ with $h|x$ and
$2x+1|2n-2x+1$ are precisely the elements of the form

$S^{b-1}G^{p+1}S^{a-1}(1,1)$

with $a,b,p\geq 1$ i.e. those with track vector $(a,(1)^{p},b).$

As in the previous Sections, we denote by $a_{n}$ the number of elements in
row $n$ of the form described in the proposition. It follows from Theorem 4.3
that $a_{n}-1$ is equal to the number of solutions to Equation 2. By the first
part of Lemma 8 in ([4]), the number of elements of the form $(n,r)$ with
track vector $((1)^{p},a,(1)^{q})$ is equal to

$ap(2q+2)+a(q+1)-p(2q+1)=2ap(q+1)+a(q+1)-2p(q+1)+p.$

If $n$ is fixed and we substitute $q+1=\hat{q}$ the number of such elements is
equal to the number of solutions of the equation

$n=2ap\hat{q}+a\hat{q}-2p\hat{q}+p=2p\hat{q}(a-1)+(a-1)\hat{q}+\hat{q}+p.$

Set $\hat{a}=a-1.$ We get the equation
$n=2p\hat{q}\hat{a}+\hat{a}\hat{q}+\hat{q}+p,$ where $\hat{a},\hat{q}\geq 1,$
and $p\geq 0.$ This equation coincides with Equation 2. ∎

######  Corollary 6.2.

The number of elements in row $n$ with track vector of the form
$(a,(1)^{p},b),$ with $a,b,p\geq 1$ is equal to the number of elements in row
$n$ with track vector of the form $((1)^{p},a,(1)^{q}),$ where $p,q\geq 0,$
$a\geq 2.$ Moreover this common value is $a_{n}-1.$

We conjecture that the sequence $a_{n}$ tends to infinity.

######  Conjecture 6.3.

$a_{n}\to\infty,$

more precisely $a_{n}\geq\lfloor\log(n)\rfloor-1.$

The inequality of the conjecture originates from numerical evidences. Notice
that it is not true that $a_{n}\geq\lfloor\log(n)\rfloor.$ In fact
$a_{18007}=8$ but $\lfloor\log(18007)\rfloor=9.$

Notice that the previous conjecture implies Conjecture 1.1 and Theorem 4.4.

Moreover, by the paper [4], it follows that the set of elements in row $n$
with track vector $((1)^{p},a,(1)^{q}),$ where $p,q\geq 0,$ $a\geq 2$
corresponds bijectively with a subset of the elementary partitions, which in
turn are a subset of the set of partitions with $n$ subpartitions. Hence, if
$s_{n}$ is the number of partitions with $n$ subparitions, the previous
conjecture implies also that $s_{n}\to\infty.$ Notice that sequence
$\\{s_{n}\\}_{n\in\mathbb{N}}$ is sequence A116473 in [7], where it is
reported that it is conjectures that $s_{n}\to\infty$. Thus Conjecture 6.3
would imply also this conjecture present in [7].

Another conjecture suggested by strong numerical evidences is the following.

######  Conjecture 6.4.

Let $c_{n}$ be the number of elements in row $n$ with breadth $3.$ Then
$c_{n}\to\infty.$

We conclude this Section with a conjecture about the possible positions of
elements created at Step $i$ inside the matrix $F.$

######  Conjecture 6.5.

Consider the elements of matrix $F$ that are created at Step $i.$ Let $r_{i}$
be the maximal index of a row of matrix $F$ containing such an element. Then
$\\{r_{2j+1}\\}_{j\in\mathbb{N}}$ is sequence A061278 in [7] and
$\\{r_{2j}\\}_{j\in\mathbb{N}}$ is sequence A001571 in [7]. Moreover, if $i$
is even, row $r_{i}$ of $F$ contains two elements created at Step $i.$ On the
other hand, if $i$ is odd, row $r_{i}$ contains one element created at Step
$i.$

######  Example 6.6.

Let $i=6.$ The maximal row containing an element created at Step 6 is row 35.
Notice that 35 is the third element (avoiding the first zero) of sequence
A001571 in [7]. Moreover, row 35 of $F$ contains two elements created at Step
6, precisely $F_{35,15}$ and $F_{35,26}.$

##  7 Upper bound for $F_{n}$

We conclude the paper improving the best known upper bound for $F_{n}.$

Corollary 5 in [2] states that $F_{n}\leq\min\\{n,\phi(2n+1)\\}$ where $\phi$
is the Euler totient function, see e.g. [1]. In fact $F_{n}\leq n$ since the
matrix $F$ is lower triangular. Moreover, it is shown in [2], that if
$F_{n,k}=1$ then $\gcd(k,2n+1)=1$ (this can also be shown easily using the
recursive definition of $F$ used in this paper). Hence $F_{n}\leq\phi(2n+1).$

It is possible to slightly improve this bound in the following way. Consider
the same notation of the proof of Theorem 2.1. Since $G(1,1)=(2,1)\in X_{1},$
$S(1,1)=(2,2)\in X_{2},$ $G(X_{1}\cup X_{2})\subseteq X_{1}$ and $S(X_{1}\cup
X_{2})\subseteq X_{2}$ we have that every element $(n,k),$ $n>1,$ such that
$F_{n,k}=1$ is contained in $X_{1}\cup X_{2}.$ In particular,
$k<\frac{n}{2}+\frac{1}{4}$ or $k>\frac{2n}{3}+\frac{1}{3}.$ Hence

$F_{n}\leq
n-\left(\frac{2n}{3}+\frac{1}{3}-\left(\frac{n}{2}+\frac{1}{4}\right)-1\right)=\frac{5n}{6}-\frac{13}{12}.$

Thus we get

$F_{n}\leq\min\left\\{\frac{5n}{6}-\frac{13}{12},\phi(2n+1)\right\\}.$

## References

  * [1] T.M. Apostol.  Introduction to Analytic Number Theory.  Undergraduate Texts in Mathematics. Springer New York, 1998.
  * [2] M. Barnabei, F. Bonetti, N. Castronuovo, and R.Cori.  Some permutations on Dyck words.  Theoretical Computer Science, 635:51–63, 2016.
  * [3] N. Castronuovo, R. Cori, and S. Labbé.  A permutation on words in a two letter alphabet.  In Combinatorics on Words - 11th International Conference, WORDS 2017, Montreal, QC, Canada, September 11-15, 2017, Proceedings, Lecture Notes in Computer Science, pages 240–251. Springer, 2017.
  * [4] R. Cori, A. Frosini, G. Palma, E. Pergola, and S. Rinaldi.  On doubly symmetric dyck words.  Under review.
  * [5] P. de la Harpe.  Topics in Geometric Group Theory.  Chicago Lectures in Mathematics. University of Chicago Press, 2000.
  * [6] R. Schoof.  Catalan’s Conjecture.  Universitext. Springer London, 2010.
  * [7] N. J. A. Sloane.  The On-Line Encyclopedia of Integer Sequences.  https://oeis.org/.