# The Timing System of LIGO Discoveries

Andrew G. Sullivan  Department of Physics, Columbia University in the City of
New York, 550 W 120th St., New York, NY 10027, USA  Yasmeen Asali  Columbia
Astrophysics Laboratory, Columbia University in the City of New York, 550 W
120th St., New York, NY 10027, USA  Zsuzsanna Márka  Columbia Astrophysics
Laboratory, Columbia University in the City of New York, 550 W 120th St., New
York, NY 10027, USA  Daniel Sigg  LIGO Hanford Observatory, Route 10, Mile
marker 2, Hanford, Washington 99352, USA  Stefan Countryman  Department of
Physics, Columbia University in the City of New York, 550 W 120th St., New
York, NY 10027, USA  Imre Bartos  Department of Physics, University of
Florida, PO Box 118440, Gainesville, FL 32611-8440, USA  Keita Kawabe  LIGO
Hanford Observatory, Route 10, Mile marker 2, Hanford, Washington 99352, USA
Marc D. Pirello  LIGO Hanford Observatory, Route 10, Mile marker 2, Hanford,
Washington 99352, USA  Michael Thomas  LIGO Livingston Observatory,
Livingston, LA 70754, USA  Thomas J. Shaffer  LIGO Hanford Observatory, Route
10, Mile marker 2, Hanford, Washington 99352, USA  Keith Thorne  LIGO
Livingston Observatory, Livingston, LA 70754, USA  Michael Laxen  LIGO
Livingston Observatory, Livingston, LA 70754, USA  Joseph Betzwieser  LIGO
Livingston Observatory, Livingston, LA 70754, USA  Kiwamu Izumi  JAXA
Institute of Space and Astronautical Science, Chuo-ku, Sagamihara City,
Kanagawa 252-0222, Japan  Rolf Bork  LIGO Laboratory, California Institute of
Technology, Pasadena, CA 91125, USA  Alex Ivanov  LIGO Laboratory, California
Institute of Technology, Pasadena, CA 91125, USA  Dave Barker  LIGO Hanford
Observatory, Route 10, Mile marker 2, Hanford, Washington 99352, USA  Carl
Adams  LIGO Livingston Observatory, Livingston, LA 70754, USA  Filiberto Clara
LIGO Hanford Observatory, Route 10, Mile marker 2, Hanford, Washington 99352,
USA  Maxim Factourovich  Department of Physics, Columbia University in the
City of New York, 550 W 120th St., New York, NY 10027, USA  Szabolcs Márka
Department of Physics, Columbia University in the City of New York, 550 W
120th St., New York, NY 10027, USA

###### Abstract

LIGO’s mission critical timing system has enabled gravitational wave and
multi-messenger astrophysical discoveries as well as the rich science
extracted. Achieving optimal detector sensitivity, detecting transient
gravitational waves, and especially localizing gravitational wave sources, the
underpinning of multi-messenger astrophysics, all require proper gravitational
wave data time-stamping. Measurements of the relative arrival times of
gravitational waves between different detectors allow for coherent
gravitational wave detections, localization of gravitational wave sources, and
the creation of skymaps. The carefully designed timing system achieves these
goals by mitigating phase noise to avoid signal up-conversion and maximize
gravitational wave detector sensitivity. The timing system also redundantly
performs self-calibration and self-diagnostics in order to ensure reliable,
extendable, and traceable time stamping. In this paper, we describe and
quantify the performance of these core systems during the latest O3 scientific
run of LIGO, Virgo, and KAGRA. We present results of the diagnostic checks
done to verify the time-stamping for individual gravitational wave events
observed during O3 as well as the timing system performance for all of O3 in
LIGO Livingston and LIGO Hanford. We find that, after 3 observing runs, the
LIGO timing system continues to reliably meet mission requirements of timing
precision below 1 $\mu$s with a significant safety margin.

##  I Introduction

The LIGO gravitational wave (GW) detectors have completed three GW observing
runs since becoming operational in 2015 Harry (2010); Aasi  _et al._ (2015);
Abbott  _et al._ (2016); Martynov  _et al._ (2016); Tse  _et al._ (2019);
Buikema  _et al._ (2020); Abbott (2020). The network of LIGO, Virgo Acernese
_et al._ (2015), GEO600 Dooley  _et al._ (2016); Affeldt  _et al._ (2014), and
KAGRA Aso  _et al._ (2013); Akutsu  _et al._ (2021) detectors has successfully
observed GWs from a large number of astrophysical sources including binary
black hole (BBH) and binary neutron star (BNS) inspirals Abbott  _et al._
(2019); LIGO Scientific Collaboration and Virgo Collaboration (2021); Abbott
_et al._ (2021).

In order to make these discoveries and coordinate between the global GW
detector and multi-messenger followup networks, both LIGO Hanford (LHO) and
LIGO Livingston (LLO) require a precise mechanism to determine timing of its
observed gravitational wave events. Not only must timing be maintained between
the global detector network, but the 4 km size of the interferometers
necessitates precise timing at all parts of the individual detector across
large distances. Consequently, the LIGO timing system was developed to ensure
precise time recording at all relevant parts of the detectors Bartos  _et al._
(2010); I. Bartos and D. Sigg (2009). The creation of the timing system was a
collaboration between Columbia University, LHO, and the Caltech and is
maintained by Columbia, LHO, and LLO.

The operation of the timing system during and in the followup of an observing
run is a mission-critical aspect of LIGO as reliable interferometer operation
and astrophysical data analysis both directly depend on it. The timing system
and its carefully selected components allow (a) phase noise to be minimized
via its precise crystal oscillators, lessening the timing contribution to the
detector noise level and consequently allowing LIGO’s astrophysical reach, (b)
the absolute timing of the data streams in the detector network to agree to
high accuracy, making coincident and coherent observation using the GW
detector network possible, (c) verification of data-stream timing across
detectors so that a sufficiently numerous network of interferometric detectors
can recover both the polarization and sky direction information for a detected
event to high accuracy and precision, and (d) quick and trustworthy timing
information on hand for multi-messenger searches for coincident detections of
GWs and other astrophysical events, such as gamma ray bursts (GRBs) or
supernovae LIGO and Virgo Collaborations (2008); Abbott B. others (2008);
Márka  _et al._ (2010); Abbott  _et al._ (2017). The timing and timing
distribution systems are essential for proper GW data collection and provide
end-to-end witness signals for wholistic assurances on data timestamps.

With three observing runs complete, the LIGO timing systems have produced a
large sum of data with which one can assess their functionality and
performance. In this paper, we discuss how the timing system and the timing
diagnostic system have performed during the third GW observing run. Other
systems outside of the timing systems, such as the interferometer components,
the photodetectors, the calibration, the filters, or the electronics, can on
occasion introduce timing delays. Analyses of the effects of these other
systems on the timing system require separate investigations, not covered by
this study.

We divide the text as follows. In Section II, we review the configuration of
the LIGO timing system. In Section III, we discuss the timing verification
studies done to assess the accuracy of the system and present the results of
these studies from O3. In Section IV, we discuss the results of the O3 timing
verification studies and conclude.

##  II Advanced LIGO Timing System

###  II.1 Timing Distribution System

The timing distribution system provides synchronized timing (a) to an absolute
time measure (UTC) so that results can be compared between LHO, LLO, other
members of the global GW-detector-network, and non-GW detectors to enable
multi-messenger astronomy; (b) to subsystems of a given detector, ensuring the
reliable operation and control of the interferometer; and (c) with minimized
data acquisition timing signal jitter. The timing distribution system thus
creates the universal, precise, and traceable time-frame in which the
components of the entire interferometer network are synchronized Marka  _et
al._ (2002); Factourovich (2007). The timing system is also redundantly cross
checked to time sources of different Allan-variance Allan (1966) to protect
against single technology failure.

The timing precision required for the LIGO detectors varies for different
science goals and evolves with discoveries of new science. Consequently, a
compromise was adopted, with an engineering specification requirement for
intra-observatory systems of better than 1 $\mu$s Bartos  _et al._ (2010)
performance at the very worst case; however, to allow for future scientific
advances, it was recommended that the timing system should achieve the best
possible performance allowed by technology and other constraints available at
the time of its design. The timing distribution system Bartos  _et al._ (2010)
has a hardware defined timing accuracy and overall clock synchronization
precision that satisfies LIGO requirements (laboratory measurement indicates
“median of 14.3 ns and a 99% confidence interval of 6.2 ns (with maximum of 24
ns and minimum of 10.5 ns)” Bartos  _et al._ (2010); I. Bartos others (2010a,
2008) deviation between the timing reference input and trigger passed to data
acquisition system (DAQ), assuming that the fiber pair used for the fiber
delay measurement is symmetric in length).

At each LIGO site, the primary synchronization reference is derived from the
signals of multiple Global Positioning System (GPS) satellites _gp (2021), as
a root source of timing. A GPS backed clock at the corner station Marka  _et
al._ (2015, 2012) receives timing information from a GPS receiver tri (2015)
and distributes it to the system. A comparison flywheel of a Cs-III atomic
clock csi (2018) is continuously monitored to identify GPS and other systemic
transient problems. These atomic clocks run fully independently from the GPS
system after their reset and initial precision calibration before an observing
run Countryman  _et al._ (2018). Since even calibrated Cs clocks display a
slight drift, these atomic clock comparisons are not used to recover absolute
time.

The timing distribution system is structured as a chain of modules beginning
from the trunk module, extending to branch modules that fan out to various
leaf modules. The trunk module receives GPS timing data from a receiver module
as a 1PPS signal and synchronizes its internal oven-controlled crystal
oscillator (OCXO) clock to the GPS time. The OCXO operates on a $2^{N}$ Hz
base frequency where $N=26$ during O3. The trunk then passes the information
to branch modules which contain a voltage-controlled crystal oscillator (VCXO)
clock. The branch modules synchronize their internal clock to the received
timing signal. Individual branch modules may fan out to as many as 16 other
branch or leaf modules Bartos  _et al._ (2010). The leaf modules receive the
timing signal from a branch module and synchronizes their internal clocks
(also a VCXO clock) to it. The leaf module passes on timing information to the
rest of the detector through the use of daughter boards. A timing converter on
the leaf module sends timing pulses (as well as Inter-Range Instrumentation
Group B (IRIG-B)I. Belopolski and D. Sigg (2010); I. Belopolski et al. (2011)
and DuoTone signals I. Bartos others (2010b); Z. Marka others (2006)) to the
LIGO DAQ. The Timing System thus allows for a plug-and-play dynamic topology,
e.g.

[.Trunk [.B I [.B D D I ] C ] C I [.B D D I C C ] D ]

where the symbol meanings are as follows: B is a Branch, C is a Comparator, I
is a IRIG-B, and D is a DuoTone-Leaf module. Figure 1 shows a diagram of the
timing system, including the path of both the timing and diagnostic signals
around the Trunk as well as at the branches and leaves.

Figure 1:  Timing System information flow. The gray dashed panels represent
different locations within the interferometer. Includes both distribution and
diagnostic signals. A Trimble GPS clock passes 1PPS signal to the trunk, which
synchronizes its OCXO clock to the signal. The trunk’s built-in GPS clock
provides a diagnostic 1PPS source as well as the GPS timestamp during normal
operation. The trunk distributes the timing signal to leaf modules (via branch
modules) through optical fibers. Leaf-DuoTone assemblies installed in I/O
chassis produce a $2^{16}$ Hz clock signal (with $<1$ $\mu$s error) and a
DuoTone signal (digitized at $2^{16}$ Hz and decimated down to $2^{14}$ Hz)
for diagnostics and calibration.

Every board in the timing distribution chain was meticulously tested by
different teams and in different environments, including end-to-end laboratory
tests using long fibers. It is essential that the accuracy of the distributed
timing signals is closely monitored to verify the accuracy of the
gravitational wave data stream and ensure that it can be correlated with other
data streams.

The LIGO detectors (and most other observatories) rely on GPS to ensure long-
term UTC synchronized timing. Consequently, there is a relatively small
additional correction to the upper limit on the inter-site timing accuracy, as
the GPS system is only guaranteed for hundreds of ns. In practice, GPS does
much better most of the time and, even if the most conservative estimate is
used, the absolute total timing discrepancy between detectors would not affect
the utility of current gravitational wave observations Bartos  _et al._
(2010). The GPS system is closely followed by multiple agencies and usually
performs at the $\sim 50$ ns level (GPS, 2008; ”WAAS T&E Team”, ). In
principle, LIGO’s timing system also allows for the detection of GPS system
problems as relevant data is recorded.

###  II.2 Timing Diagnostic System

The mission critical nature of the LIGO timing distribution system requires
the system’s status be closely monitored, periodically tested in-depth, and
traceable. The timing diagnostic system has the following major components:

1\. Self Diagnostics — The timing system has extensive and continuously
recorded self-diagnostic information implemented in hardware. Every element in
the timing distribution chain sends back detailed diagnostic information (as
shown in Figure 1) which is archived and also available through Motif Editor
and Display Manager (MEDM) screens in the LIGO Control Room. The collected
information includes diagnostics such as fiber delays and control voltage for
the different flywheels within the system. Additionally, information about the
structure, topology, and configuration of the system as a whole is monitored
and archived along with the connection and up/down status of each node. MEDM
screens in the LIGO control rooms show if errors are present in real time.
This self-diagnostic data is available for further analysis and
characterization.

2\. Multiple, cross-verified time sources — Many test-points of the timing
distribution system are compared to independent time sources of different
manufacturer, firmware, type, and location. These include additional GPS
synchronized time sources connected to independent GPS antennae and a Cs-III
atomic clock at each site. The workhorses of the timing diagnostic system are
the timing comparators S. Countryman others (2012). They compare 1PPS signals
from many devices to the 1PPS signal from the timing distribution chain with
high precision. The comparator timing chassis reports the measured time
differences in every second that is recorded along with the other diagnostic
information mentioned above.

3\. Timing diagnostics — There are several additional hardware-generated
synchronized timing witness channels available for timing diagnostics, such as
the so-called DuoTone signals produced on each Leaf-DuoTone R. Mitra and Z.
Marka (2010) assembly within each LIGO analogue-to-digital converter (ADC)
chassis. DuoTone signals are digitized and recorded along with the GW data
channel as a witness of precise timing. The phase of the DuoTone signal allows
sub-microsecond accurate determination of the digital datastream’s shift from
perfect agreement with the UTC time.

An additional witness is the IRIG-B I. Belopolski and D. Sigg (2010); I.
Belopolski et al. (2011) signal. The timing distribution system itself
includes IRIG-B interfaces, which produce IRIG-B signals used for
communicating with devices that require IRIG-B input, including some computer
interfaces. The independent GPS sources at the End Stations also have IRIG-B
output capability for added redundancy and accountability. The IRIG-B signal
has a phase that allows time verification on the ms level while its full
timecode allows the determination of absolute YEAR:MONTH:DAY-
HOUR:MINUTE:SECOND unambiguously. Independent IRIG-B signals at the End
Stations are digitized and used to verify the timestamp provided by the timing
distribution system.

The timing diagnostics hardware records multiple robust diagnostics and
witness signals covering all possible time-shifts. It also provides
independent verification of the accuracy and validity of the recorded
timestamp for a particular piece of data.

##  III Timing Verification Studies

We now discuss the various timing verification studies conducted during the
observing runs of LIGO and present the results of these studies from O3.

DuoTone Delay Checks— When precision measurement of sub-sample timing in a
digital system is required, sinusoid-shaped witness signals are well suited
due to their low impact. To measure longer times than the period of a
sinusoid, multiple sinusoids of slightly different frequencies can be added,
extending the range of measurement. The Leaf-DuoTone assembly provides a two
tone signal with frequencies 960 Hz and 961 Hz Bartos  _et al._ (2010). This
choice bridges the gap between the IRIG-B’s subsecond accuracy and the
system’s reach into the ns range, giving us the ability to characterize delays
over 16 orders of magnitudes, from ns to years. The use of a sinusoid timing
signal composed of only two high frequency lines mitigates potential DAQ
crosstalk within the frequency range of expected astrophysical binaries.
Additionally, these frequencies are chosen around 960 Hz to coincide with the
higher harmonics of the 60 Hz power-line frequency, which already contaminates
LIGO’s bandwidth.

The coincident zero crossing time of the DuoTone signals are hardware
synchronized to the GPS 1PPS rising edge. The use of only two frequencies
allows for unambiguous delay measurement at the second scale, providing
precision enhancement to IRIG-B. Of course, TriTone or QuadTone signals can go
beyond the second scale limitation of DuoTone without compromising precision
significantly. The digitized DuoTone diagnostic signal is compared with GPS
timing. Deviations between the DuoTone zero crossing time and GPS 1PPS rising
edge may be observed with ns precision. The DuoTone diagnostic signal $Y$ may
be represented as follows

$Y_{1}=A\sin{(2\pi\times 960(t-\Delta t))}$ (1a) $Y_{2}=A\sin{(2\pi\times
961(t-\Delta t))}$ (1b) $Y=Y_{1}+Y_{2}+\Delta A$ (1c)

where $A$ is the amplitude of the DuoTone signals with a value of $2.5$ V,
$\Delta A$ is centered at $0$ V, and $\Delta t$ is the phase difference
between the DuoTone signal and the GPS 1PPS rising edge Z. Marka others
(2006). The DuoTone signal naturally obtains a delay from the GPS time. The
expected delay, as measured Z. Marka others (2006) on a set of characteristic
board combinations, is $50.25$ $\mu$s (6.70 $\mu$s from the designed-in delay
between the DuoTone signal and the timing branch and $43.55$ $\mu$s from the
65536 Hz to 16384 Hz decimation filter at 960 Hz Zsuzsanna Marka (2017)). The
residual delay after subtracting $50.25$ $\mu$s from $\Delta t$ at each time
segment is the uncertainty in the timing measurement. Figure 2 shows a plot of
Equation 1c. As Figure 2 shows, the zero crossing time in the center of a
pulse occurs once per second, so the time difference $\Delta t$ between the
zero crossing time and the time of the GPS 1PPS rising edge can be measured
for each second.

Figure 2: Plots of a simulated DuoTone diagnostic signal that would be created
by the Leaf-DuoTone board including a characteristic offset $\Delta t$. (Top)
Two seconds of the DuoTone signal. (Bottom) A closeup around the zero crossing
time of the DuoTone signal, with the time shifted so that $t=0$ is at the time
of the GPS 1PPS signal rising edge. The time of the GPS 1PPS rising edge and
the zero-crossing time are marked on the plot.

DuoTone delay checks are always performed in low-latency for the interval of 5
minutes before and after a GW event to ensure that the GPS time-stamping of
events is highly accurate at the detectors. We perform DuoTone delay checks
for all GW event candidates, observing the residual time difference between
the GPS 1PPS rising edge and DuoTone zero crossing time. Checks are performed
at the Corner Stations of both LHO and LLO at a point close to a digitizer
where the most critical signals for gravitational-wave detection are recorded.
Checks are also performed at the X and Y End Stations of both LHO and LLO at
points close to digitizers that record mission critical signals for the
calibration of the detectors (Karki, 2016). For each check, we create a
histogram for the observed residual delay over the course of the $\pm 5$
minutes of the GW event. Figure 3 shows a DuoTone histogram at the Corner
Station of LHO during the $\pm 5$ minutes of GW200115, one of the Neutron
Star-Black Hole merger events observed in O3B Abbott  _et al._ (2021). Plots
like this are also made for the DuoTone delay at the X and Y End Stations of
both detectors. As the plot demonstrates, the residual times observed for
GW200115 were well below the 1 $\mu$s threshold at LHO and thus GW200115 is
properly time-stamped at that detector.

Figure 3: DuoTone delay histogram for the Corner Station at LHO in the $\pm 5$
minutes surrounding GW200115 with mean delay $\mu$ subtracted. The standard
deviation $\sigma$ is also reported in the legend. The residual time at the GW
event time is denoted by the position of the red line.

Figure 4 shows histograms of the average time delay over the $\pm 5$ minutes
around every GW event in O3. We also plot histograms of the difference between
the DuoTone delay at the event time and the average delay around that event in
Figure 5. The DuoTone checks returned residual time variations below 1 $\mu$s
in the ADC channels for all GW events of O3 at both LLO and LHO. The average
delay of each event never differed from the overall mean delay by more than
$\pm 20$ ns at any location. Furthermore, the difference between the delay at
the event time and average event delay never exceeded $\pm 1.1$ ns.
Consequently, the DuoTone checks demonstrate timing precision within the
designed threshold Bartos  _et al._ (2010) for all GW events in O3. These
checks were performed for GW event candidates in previous observing runs as
well Countryman, S., Marka, Z., Lazar, J. (2016); Countryman, S., Marka, Z.,
Kawabe K. (2015); Countryman (2017a, b, c); Countryman  _et al._ (2017a, b, c,
d, e, f, g, h, i, j, k, 2016); Countryman, S. and others (2015).

Figure 4: The average ADC DuoTone time delay $\pm 5$ minutes around all GW
event observed during O3 in H1 (Top) and L1 (Bottom). Each bin contains the
number of GW events with a certain average time delay. The mean delay across
all events $\mu$ has been removed. The legend of each subplot shows $\mu$
along with its standard deviation $\sigma$. Each subplot shows the delay in a
different location denoted by the plot title.

Figure 5: The differences between the DuoTone delay at the GW event times and
the average DuoTone time delay in the $\pm 5$ minutes around the GW events
observed during O3 in H1 (Top) and L1 (Bottom). Each subplot shows the delay
difference at a different detector location.

IRIG-B Checks– IRIG-B timing verification checks function by decoding the
IRIG-B interface’s time-stamping (converted from the internal LIGO timing
system signal encoding) and comparing it with GPS time to ensure that at least
on the order of ms the LIGO timing system remains aligned with GPS time.
Because the IRIG-B signal has ms precision due to a measurable phase, it may
be used as a corroborative check in addition to the DuoTone checks to ensure
there are no timing issues around GW events.

The IRIG-B encoded signal produces high and low voltage pulses. The length of
these pulses determines whether a given pulse corresponds to a value of 0, 1,
or a control character. A short high voltage pulse corresponds to a value of
0, a long high voltage pulse corresponds to a value of 1, and a very long
pulse corresponds to a control. The control pulses regulate the phase of the
IRIG-B signal. Additionally, for each unit of time (seconds, minutes, etc.) of
the timestamp, a high voltage pulse corresponds to the number of that unit. To
obtain the time encoded manually, one must add the time values of each long
pulse for each unit of time.

For each GW event observed by LIGO, the IRIG-B time at the End Station of each
interferometer is checked against the GPS time in the 30 second window
surrounding the time of the GW event. For all GW events in O3, the IRIG-B
output time matched the GPS time. We observed no issues with the IRIG-B
timestamping at either LLO or LHO for any of the GW candidates observed in O3.
We note, however, there was a persistent firmware problem in the LHO Y End
Station CNS II clock that affected the IRIG-B timing output. When the IRIG-B
time changed from 23:59:59 to 0:00:00, the IRIG-B would output the incorrect
time at 0:00:00, but would output the correct time at all other times of the
day. This issue was identified in LLO and LHO prior to O3; however, it was
only fixed in LLO Countryman and Márka (2017) and thus remained in the LHO Y
End Station. After O3 was completed, the issue was fixed in LHO as well. As
this was an issue with the diagnostic CNS II clock, not the timing system
itself and none of the GW events coincided with the times of this issue, the
timing system’s performance and all GW event data remain unaffected.

Slow Channel Checks– Throughout an observing run, the 1PPS signals from the
timing distribution are continuously compared with independent GPS clocks at
various locations in the LIGO detectors. This ensures that the clocks at the
various stations are properly synchronized and that timing of data and systems
at different parts of the LIGO detectors properly correspond to GPS time. The
three most important clocks considered in these checks are the GPS backed NTP
server clock NTP (2016) found in the computer room of the Corner Station of
the LIGO detectors and the CNS II GPS clocks CNS (2021) housed at the two End
Stations of each LIGO detector. The time difference between these clocks and
the LIGO timing distribution’s 1PPS signal is recorded throughout the
observing runs. Assessments of the slow channel timing performance have been
conducted for O1 and O2 Countryman  _et al._ (2017l); Countryman and Marka
(2017a); Countryman  _et al._ (2017m); Countryman and Marka (2017b) as well as
O3A Asali  _et al._ (2019) and O3B Sullivan  _et al._ (2021).

Figure 6 shows plots used to track the timing performance for LHO throughout
O3. Figure 6 includes the time difference between the timing system and the
CNS II GPS clocks at each End Station and the NTP Server. At the corner
station and Y End Station during O3A, the timing variation was within $\pm$ 80
ns, well below the 1 $\mu$s performance threshold. At the X End Station during
O3A all but one time segment showed variation below the 1 $\mu$s threshold.
This outlier was due to a GPS antenna issue on July 8, 2019 when the antenna
was momentarily tracking zero satellites and the CNS II clock returned faulty
timing data. At the corner station and X End Station during O3B, the time
difference was always within the 1 $\mu$s threshold. At only one time during
the run did the time difference exceed the 1 $\mu$s threshold at the LHO Y End
Station. This coincides with a DAQ restart on February 26, 2020. Besides this
anomaly, the time difference between the GPS clocks and timing system at LHO
was below $\pm 150$ ns throughout O3B, with the overwhelming majority of time
differences below $\pm 80$ ns.

Figure 6: Plots of the timing difference between the LHO timing system 1PPS
signal and various GPS clocks during O3, including (Top) time difference
between the GPS-backed NTP Server and the timing system at the Corner Station,
(Middle) time difference between a GPS-backed CNS II clock and the timing
system at the X End Station, and (Bottom) time difference between a GPS-backed
CNS II clock and the timing system at the Y End Station. O3A results are on
the left and O3B results are on the right. The green dots represent the
average time difference over the course of one lock segment, the error bars
denote standard deviation of the average time difference, and the blue and red
triangles denote the minimum and maximum time differences in each lock
segment. The yellow line corresponds to a time when data was not taken in this
channel and the light blue line corresponds to a time where the time
difference exceeded the 1 $\mu$s threshold. The outlier at the X End Station
98 days into O3A was caused by a GPS antenna issue where the antenna was
briefly tracking 0 satellites and the outlier at the Y End Station 117 days
into O3B was the result of a DAQ restart. The data not taken marker at 117
days of O3B on the NTP server and X End plots were due to the same DAQ
restart. The data not taken marker 38 days into O3B on the Y End Station plot
was caused by a failure in the fiber link between the slow controls Beckhoff
chassis at the Y End Station.

Figure 7 shows plots used to track the timing performance at LLO during O3.
Figure 7 includes the time difference between the timing system and the CNS II
GPS clock at the X End Station and the NTP Server. We omit the plots for the Y
End Station because an issue whose origin is external to the timing system
arose with the Y End redundant CNS II clock which caused repeated timing
errors on the order of $10^{-1}$ s in every lock segment of O3. To confirm
that the issue was with the CNS II GPS Clock and not the timing system, we ran
DuoTone delay checks at times in both O3A and O3B where these persistent
errors took place and found that the DuoTone delay returned the expected
delays within the 1 $\mu$s threshold.

At the LLO Corner Station and X End Station during O3A, all time variations
were well within the $\pm$1 $\mu$s threshold. The Corner Station showed
variation within $\pm$110 ns at all times and the X End Station showed
variation within $\pm$80 ns at all times. At the Corner Station during O3B,
the time difference was below the $\pm 1$ $\mu$s threshold throughout the run
and, for the vast majority of times, was below $\pm 100$ ns. At the X End
Station, there were 7 times in O3B during which the time difference exceeded
the $1$ $\mu$s. These errors arose due to an issue with the X End Station GPS
antenna connected to the CNS II clock and correspond to periods of time when
the antenna was tracking between 2 and 0 satellites and providing unreliable
GPS timing data. Additionally, a number of minima and maxima on the X End
Station plot in Figure 7 exceeded $\pm 200$ ns. The same GPS antenna issue
caused the large scatter in the minima and maxima of lock segment time
differences, as the GPS antenna was tracking two or fewer satellites at those
times. None of these errors coincided with a GW event. Otherwise, for much of
O3B, the time difference at the X End Station was within $\pm 100$ ns.

Figure 7: Plots of the timing difference between the LLO timing system 1PPS
signal and various GPS clocks during O3, including (Top) time difference
between the GPS-backed NTP Server and the timing system at the Corner Station
and (Bottom) time difference between a GPS-backed CNS II clock and the timing
system at the X End Station. O3A results are on the left and O3B results are
on the right. The green dots represent the average time difference over the
course of one lock segment, the error bars denote standard deviation of the
average time difference, and the blue and red triangles denote the minimum and
maximum time difference in each lock segment. The yellow line corresponds to a
time when data was not taken in the channel and the light blue line
corresponds to a time where the time difference exceeded the 1 $\mu$s
threshold. All outliers in the X End Station plot were the result of GPS
antenna issues as the antenna was tracking two or fewer satellites during
those times. The data not taken lines in the O3A plots were caused by 1) a
Beckhoff communication failure on April 1, 2019, 2) lock loss prior to
preventative maintenance on April 8, 2019, 3) Beckhoff failure which caused
lock loss on April 20, 2019, and 4) a DAQ process restart on September 20,
2019. The data not taken lines in the O3B plots were caused by 1) a DAQ
process restart on December 5, 2019, 2) a Beckhoff connection issue which
caused lock loss on December 21, 2019, 3) a DAQ restart on January 17, 2020,
4) a Beckhoff connection issue which caused lock loss on February 3, 2020, 5)
a data concentrator failure and restart on February 23, 2020, 6) a DAQ screen
meltdown and reset on March 6, 2020, 7) a DAQ screen meltdown and reset on
March 11, 2020, 8) a DAQ restart on March 15, 2020, 9) a DAQ error on March
17, 2020, 10) a DAQ error on March 17, 2020 and 11) a DAQ restart on March 24,
2020.

In addition to checking the timing system against GPS clocks at various
stations, the timing at a given interferometer is verified against an on-site
Cs-III atomic clock csi (2018). The Cs-III atomic clock is very precise on
short time-scales; however, the Cs-III clock time drifts over the course of an
observing run due to various environmental factors. In order to obtain
accurate measurements of the deviation from the atomic clock time, the atomic
drift trend is subtracted. Figure 8 shows a histogram of the average timing
system variation from the Cs-III time (with the trend removed) for each minute
of O3 (excluding minutes when timing data was unrecorded) at LLO and LHO. The
timing variation between the atomic clock and timing system was always within
$\pm$80 ns at both LHO and LLO during O3.

Figure 8: Histograms of the average time difference in every minute of O3
between the timing system and the time of the on-site Cs-III atomic clock with
the drift trends removed in (Top) LHO and (Bottom) LLO. The left side shows
O3A while the right shows O3B.

##  IV Conclusion

Throughout O3, the LIGO timing system displayed excellent timing precision.
The DuoTone delay and IRIG-B checks confirmed that the timing system
contributed less than $\pm$1 $\mu$s to the total error in the GW arrival times
during observed GW events. Consequently, the astrophysical results for the O3
GW events are not limited by timing precision.

The long term performance of the timing system was well within the designed
specifications. The overwhelming majority of times throughout both O3A and O3B
displayed timing errors of less than $\pm$1 $\mu$s at both LLO and LHO, and in
most cases the system performed much better. General control system and GPS
antenna issues affected timing system data during the run, but these
problematic times were diagnosed. None coincided with GW events as they were
confined to a minuscule fraction of the observing run. Most importantly, these
issues were external to the timing system.

In fact, the precision and consistency of the timing system allowed us to
diagnose issues with other devices such as GPS antennae and external GPS
clocks. In addition to its excellent time-keeping ability, the timing system
serves as an investigative tool to study errors in other parts of the
instrument.

Through three complete observing runs, the LIGO timing distribution has
successfully provided critical information for the astrophysical discoveries
of LIGO. The timing system met and even exceeded mission requirements. This
precise timing information provided to the interferometers enabled the first
recorded detections of GW transients and will continue to allow for GW
detections in upcoming observing runs.

## Acknowledgments

This material is based upon work and data supported by NSF’s LIGO Laboratory
which is a major facility fully funded by the National Science Foundation.
LIGO is funded by the U.S. National Science Foundation. Virgo is funded by the
French Centre National de Recherche Scientifique (CNRS), the Italian Istituto
Nazionale della Fisica Nucleare (INFN) and the Dutch Nikhef, with
contributions by Polish and Hungarian institutes.

The authors are grateful for the LIGO Scientific Collaboration review of the
paper and this paper is assigned a LIGO DCC number(LIGO-P2200388).

Special thanks to Evan Goetz and Shivaraj Kandhasamy for their help.

The authors are grateful to the Operation Specialists of the LIGO Hanford and
Livingston observatories for their extraordinary efforts that make
observations possible. The authors would like to thank Jonathan Hanks, Patrick
Thomas, Corey Gray, Stuart Aston, and Erik R. G. von Reis for their
contributions.

The authors acknowledge the LIGO Collaboration for the production of data used
in this study and the LIGO Laboratory for data generation on its computing
resources (National Science Foundation Grants PHY-0757058 and PHY-0823459).
The authors are grateful to the LIGO DAQ, Commissioning and Detector
Characterization Teams and LSC domain expert Colleagues whose fundamental work
on the LIGO detectors enabled the data used in this paper. The authors would
like to thank colleagues of the LIGO Scientific Collaboration and the Virgo
Collaboration for their help and useful comments with special emphasis on
Colleagues at the LIGO Hanford and Livingston Observatories. The authors would
like to acknowledge the critical contributions Paul Schwinberg of LHO.

The authors thank Columbia University in the City of New York for their
generous support. The Columbia Experimental Gravity group is grateful for the
generous support of the National Science Foundation under grant PHY-1708028.
A.S. is grateful for the support of the Columbia College Science Research
Fellows program and the Heinrich, CC Summer Research Fellowship. Y.A.
acknowledges the support of a Grant-In-Aid of Research from Sigma Xi, The
Scientific Research Society. I.B. acknowledges the support of the Alfred P.
Sloan Foundation and NSF grants PHY-1911796, PHY-2110060, and PHY-2207661.

We would like to thank all of the essential workers who put their health at
risk during the COVID-19 pandemic, without whom we would not have been able to
complete this work.

## References

  * Harry (2010) G. Harry (LIGO Scientific Collaboration), Classical and Quantum Gravity 27, 084006 (2010).
  * Aasi  _et al._ (2015) J. Aasi, B. Abbott, R. Abbott, T. Abbott, M. Abernathy, K. Ackley, C. Adams, T. Adams, P. Addesso, R. Adhikari, _et al._ , Classical and Quantum Gravity 32, 074001 (2015), arXiv:1411.4547 [gr-qc] .
  * Abbott  _et al._ (2016) B. Abbott _et al._ , Phys. Rev. Lett. 116, 131103 (2016), arXiv:1602.03838 [gr-qc] .
  * Martynov  _et al._ (2016) D. Martynov _et al._ , Phys. Rev. D 93, 112004 (2016), arXiv:1604.00439 [astro-ph.IM] .
  * Tse  _et al._ (2019) M. Tse _et al._ , Phys. Rev. Lett. 123, 231107 (2019).
  * Buikema  _et al._ (2020) A. Buikema _et al._ , Phys. Rev. D 102, 062003 (2020), arXiv:2008.01301 [astro-ph.IM] .
  * Abbott (2020) B. Abbott, Living Reviews in Relativity 23, 3 (2020).
  * Acernese  _et al._ (2015) F. Acernese, M. Agathos, K. Agatsuma, D. Aisa, N. Allemandou, A. Allocca, J. Amarni, P. Astone, G. Balestri, G. Ballardin, _et al._ , Classical and Quantum Gravity 32, 024001 (2015), arXiv:1408.3978 [gr-qc] .
  * Dooley  _et al._ (2016) K. Dooley _et al._ , Classical and Quantum Gravity 33, 075009 (2016), arXiv:1510.00317 [physics.ins-det] .
  * Affeldt  _et al._ (2014) C. Affeldt _et al._ , Classical and Quantum Gravity 31, 224002 (2014).
  * Aso  _et al._ (2013) Y. Aso, Y. Michimura, K. Somiya, M. Ando, O. Miyakawa, T. Sekiguchi, D. Tatsumi, and H. Yamamoto (The KAGRA Collaboration), Phys. Rev. D 88, 043007 (2013), arXiv:1306.6747 [gr-qc] .
  * Akutsu  _et al._ (2021) T. Akutsu _et al._ , Progress of Theoretical and Experimental Physics 2021, 05A101 (2021), arXiv:2005.05574 [physics.ins-det] .
  * Abbott  _et al._ (2019) B. P. Abbott _et al._ (LIGO Scientific Collaboration and Virgo Collaboration), Phys. Rev. X 9, 031040 (2019).
  * LIGO Scientific Collaboration and Virgo Collaboration (2021) LIGO Scientific Collaboration and Virgo Collaboration, Physical Review X 11, 021053 (2021), arXiv:2010.14527 [gr-qc] .
  * Abbott  _et al._ (2021) R. Abbott _et al._ (The LIGO Scientific Collaboration and the Virgo Collaboration and the KAGRA Collaboration), arXiv e-prints , arXiv:2111.03606 (2021), arXiv:2111.03606 [gr-qc] .
  * Bartos  _et al._ (2010) I. Bartos, R. Bork, M. Factourovich, J. Heefner, S. Márka, Z. Márka, Z. Raics, P. Schwinberg, and D. Sigg, Classical and Quantum Gravity 27, 084025 (2010).
  * I. Bartos and D. Sigg (2009) I. Bartos and D. Sigg, “Diagnostics Information for the Advanced LIGO Optical Timing Distribution System,”  (2009), lIGO Document LIGO-E0900036.
  * LIGO and Virgo Collaborations (2008) LIGO and Virgo Collaborations, Classical and Quantum Gravity 25, 114051 (2008), arXiv:0802.4320 [gr-qc] .
  * Abbott B. others (2008) Abbott B. others, Astrophysical Journal 681, 1419 (2008).
  * Márka  _et al._ (2010) S. Márka, LIGO Scientific Collaboration, and Virgo Collaboration, in  _Journal of Physics Conference Series_, Journal of Physics Conference Series, Vol. 243 (2010) p. 012001.
  * Abbott  _et al._ (2017) B. P. Abbott _et al._ (LIGO Scientific Collaboration and Virgo Collaboration), Phys. Rev. Lett. 119, 161101 (2017).
  * Marka  _et al._ (2002) S. Marka, A. Masserot, and B. Mours,  _Measurement of the Time Offset Between the LIGO and VIRGO Data Acquisition Systems_ (2002).
  * Factourovich (2007) M. Factourovich,  _Timing Synchronization for Advanced LIGO Timing System_ (2007).
  * Allan (1966) D. W. Allan, IEEE Proceedings 54, 221 (1966).
  * I. Bartos others (2010a) I. Bartos others, “Testing procedure for the Timing Master/FanOut Chassis for Advanced LIGO,”  (2010a), LIGO Document T080083.
  * I. Bartos others (2008) I. Bartos others, “Test Result Description Document for the Advanced LIGO Optical Timing Distribution System,”  (2008), LIGO Document T0900050.
  * _gp (2021) “GPS.gov,”  (2021).
  * Marka  _et al._ (2015) Z. Marka, R. Mitra, S. Marka, and M. Factourovich,  _Advanced LIGO Timing System GPS Module Chassis Assembly Drawing_ (2015).
  * Marka  _et al._ (2012) Z. Marka, S. Marka, and M. Factourovich,  _Testing Procedure for aLIGO Timing GPS Module D1002546_ (2012).
  * tri (2015) _Bullet III GPS L1 Band Antenna_ , Trimble (2015).
  * csi (2018) _CsIII Atomic Clock (4310B)_ , Microsemi (2018), rev. B.
  * Countryman  _et al._ (2018) S. Countryman, J. Lazar, Z. Marka, and K. R. Corley,  _Cs-III Atomic Clock Calibration Procedure_ (2018).
  * I. Belopolski and D. Sigg (2010) I. Belopolski and D. Sigg, “Advanced LIGO Timing IRIG-B Interface Module,”  (2010), LIGO Document T1000477.
  * I. Belopolski et al. (2011) I. Belopolski et al., “Test Procedure for the IRIG-B Interface Module of the Advanced LIGO Timing System,”  (2011), LIGO Document 1100574.
  * I. Bartos others (2010b) I. Bartos others, “Test procedure for the Clock, Gate, and DuoTone Signal Interface for Advanced LIGO,”  (2010b), LIGO Document E0900019.
  * Z. Marka others (2006) Z. Marka others, “Laboratory Baseline Characterization of aLIGO’s DuoTone witness signals,”  (2006), LIGO Document T1500513.
  * GPS (2008) “Global positioning standard positioning service performance standard,”  (2008).
  * (38) ”WAAS T&E Team”, “Global Positioning System (GPS) Standard Positioning Service (SPS) Performance Analysis Report,” Performance Analysis Report.
  * S. Countryman others (2012) S. Countryman others, “The Advanced LIGO Timing System Timing Comparator/Radio Frequency Counter Module,”  (2012), LIGO Document T1200331.
  * R. Mitra and Z. Marka (2010) R. Mitra and Z. Marka, “Pre-shipment Test Procedure for the Advanced LIGO Timing System Single Slave Boards and Slave-DuoTone Assemblies,”  (2010), LIGO Document T1000670.
  * Zsuzsanna Marka (2017) Zsuzsanna Marka (LIGO Scientific Collaboration), “DuoTone Timing Witness Signal during O2,”  (2017).
  * Karki (2016) S. e. a. Karki, Review of Scientific Instruments 87, 114503 (2016), arXiv:1608.05055 [astro-ph.IM] .
  * Abbott  _et al._ (2021) R. Abbott _et al._ , The Astrophysical Journal Letters 915, L5 (2021).
  * Countryman, S., Marka, Z., Lazar, J. (2016) Countryman, S., Marka, Z., Lazar, J., “Timing Witness Signals Indicate Trustworthy Timing for G211117, a BBH Event Candidate,”  (2016).
  * Countryman, S., Marka, Z., Kawabe K. (2015) Countryman, S., Marka, Z., Kawabe K., “Timing Witness Signals Indicate Trustworthy Timing for G184098, a BBH Event Candidate,”  (2015).
  * Countryman (2017a) S. Countryman,  _Timing Witness Signals Indicate Trustworthy Timing for G299232, a GW Event Candidate_ (2017a).
  * Countryman (2017b) S. Countryman,  _Timing Witness Signals Indicate Trustworthy Timing for G298936, a GW Event Candidate_ (2017b).
  * Countryman (2017c) S. Countryman,  _Timing Witness Signals Indicate Trustworthy Timing for G298389, a GW Event Candidate_ (2017c).
  * Countryman  _et al._ (2017a) S. Countryman _et al._ ,  _Timing Witness Signals Indicate Trustworthy Timing for GW170817/G298048, a BNS Event Candidate_ (2017a).
  * Countryman  _et al._ (2017b) S. Countryman _et al._ ,  _Timing Witness Signals Indicate Trustworthy Timing for GW170814/G297595, a BBH Event Candidate_ (2017b).
  * Countryman  _et al._ (2017c) S. Countryman _et al._ ,  _Timing Witness Signals Indicate Trustworthy Timing for Candidate G296853_ (2017c).
  * Countryman  _et al._ (2017d) S. Countryman _et al._ ,  _Timing Witness Signals Indicate Trustworthy Timing for G268556, a BBH Event Candidate_ (2017d).
  * Countryman  _et al._ (2017e) S. Countryman _et al._ ,  _Timing Witness Signals Indicate Trustworthy Timing for Candidate G288732_ (2017e).
  * Countryman  _et al._ (2017f) S. Countryman _et al._ ,  _Timing Witness Signals Indicate Trustworthy Timing for Candidate G284239_ (2017f).
  * Countryman  _et al._ (2017g) S. Countryman _et al._ ,  _Timing Witness Signals Indicate Trustworthy Timing for Candidate G277583_ (2017g).
  * Countryman  _et al._ (2017h) S. Countryman _et al._ ,  _Timing Witness Signals Indicate Trustworthy Timing for Candidate G275697_ (2017h).
  * Countryman  _et al._ (2017i) S. Countryman _et al._ ,  _Timing Witness Signals Indicate Trustworthy Timing for Candidate G275404_ (2017i).
  * Countryman  _et al._ (2017j) S. Countryman _et al._ ,  _Timing Witness Signals Indicate Trustworthy Timing for Candidate G274296_ (2017j).
  * Countryman  _et al._ (2017k) S. Countryman _et al._ ,  _Timing Witness Signals Indicate Trustworthy Timing for Candidate G270580_ (2017k).
  * Countryman  _et al._ (2016) S. Countryman _et al._ ,  _Timing Witness Signals Indicate Trustworthy Timing for G211117, a BBH Event Candidate_ (2016).
  * Countryman, S. and others (2015) Countryman, S. and others, “Timing Witness Signals Indicate Trustworthy Timing for G184098, a BBH Event Candidate,”  (2015).
  * Countryman and Márka (2017) S. Countryman and Z. Márka,  _Firmware Bug in CNS II Clock IRIG-B Output in UTC Mode_ (2017).
  * NTP (2016) _GPS Network Time Server_ , Microsemi (2016).
  * CNS (2021) _CNS Clock II_, CNS Systems Inc. (2021).
  * Countryman  _et al._ (2017l) S. Countryman, Z. Marka, and S. Marka,  _aLIGO Timing System’s Accuracy during O1_ (2017l).
  * Countryman and Marka (2017a) S. Countryman and Z. Marka,  _aLIGO Timing System’s Accuracy during O2_ (2017a).
  * Countryman  _et al._ (2017m) S. Countryman, Z. Marka, and S. Marka,  _aLIGO Timing Distribution System’s Performance During O1: Atomic Clock Diagnostics_ (2017m).
  * Countryman and Marka (2017b) S. Countryman and Z. Marka,  _aLIGO Timing Distribution System’s Performance During O2: Atomic Clock Diagnostics_ (2017b).
  * Asali  _et al._ (2019) Y. Asali, S. Countryman, and Z. Marka,  _aLIGO Timing System Checks During O3A_ (2019).
  * Sullivan  _et al._ (2021) A. Sullivan, Y. Asali, S. Countryman, and Z. Marka,  _aLIGO Timing System Checks During O3B_ (2021).


Borel complexity of the family of attractors for weak IFSs

By

Paweł Klinga and Adam Kwela

###### Abstract

This paper is an attempt to measure the difference between the family of
iterated function systems attractors and a broader family, the set of
attractors for weak iterated function systems. We discuss Borel complexity of
the set wIFSd of attractors for weak iterated function systems acting on
$[0,1]^{d}$ (as a subset of the hyperspace $K([0,1]^{d})$ of all compact
subsets of $[0,1]^{d}$ equipped in the Hausdorff metric). We prove that wIFSd
is $G_{\delta\sigma}$-hard in $K([0,1]^{d})$, for all $d\in\mathbb{N}$. In
particular, wIFSd is not $F_{\sigma\delta}$ (in contrast to the family IFSd of
attractors for classical iterated function systems acting on $[0,1]^{d}$,
which is $F_{\sigma}$). Moreover, we show that in the one-dimensional case,
wIFS1 is an analytic subset of $K([0,1])$. ††2010 Mathematics Subject
Classification: Primary: 26A18. Secondary: 03E15, 28A05, 28A80.  ††Key words
and phrases: attractors, iterated function systems, Borel sets, analytic sets

##  1 Introduction

In [1, Theorem 3.9] (see also [2]) E. D’Aniello and T.H. Steele proved that
the family IFSd of attractors for iterated function systems acting on a metric
space $[0,1]^{d},$ $d\in\mathbb{N},$ is a meager $F_{\sigma}$ subset of the
space $K([0,1]^{d})$ of compact subsets of $[0,1]^{d}$ equipped with the
Hausdorff metric (note that in [10, Theorem 5] it is stated that IFSd is a
nowhere dense $F_{\sigma}$ subset of $K([0,1]^{d})$, which is not true as IFSd
is dense – it contains all finite subsets of $[0,1]^{d}$; cf. [3, Lemma 4.3]).
In [6, Theorem 4.1] it is shown that the family wIFSd of attractors for weak
iterated function systems acting on $[0,1]^{d},$ $d\in\mathbb{N},$ is also
meager. Thus, wIFSd contains the meager $F_{\sigma}$ set IFSd and is contained
in another meager $F_{\sigma}$ subset of $K([0,1]^{d})$.

Our main aim is to measure the difference between the families IFSd and wIFSd.
This paper is an attempt to calculate the descriptive complexity of wIFSd. We
prove that wIFS1 is a $G_{\delta\sigma}$-hard analytic subset of $K([0,1])$
and wIFSd, for $d>1$, is a $G_{\delta\sigma}$-hard subset of $K([0,1]^{d})$.
In particular, wIFSd is not $F_{\sigma\delta}$, which shows that it is a more
complicated object than IFSd.

In Section 2 we provide some background needed in our considerations. All
results are proved in Section 3.

##  2 Preliminaries

###  2.1 Binary sequences

By $\\{0,1\\}^{\mathbb{N}}$ we denote the family of all sequences
$\alpha:\mathbb{N}\to\\{0,1\\}$. Similarly, $\\{0,1\\}^{n}$ is the family of
all sequences $\alpha:\\{1,\ldots,n\\}\to\\{0,1\\}$ of length $n$ and we use
the symbol $\\{0,1\\}^{<\mathbb{N}}$ for the family of all finite sequences of
zeros and ones, i.e., $\\{0,1\\}^{<\mathbb{N}}=\bigcup_{n}\\{0,1\\}^{n}$.

If $s$ is a finite sequence of real numbers then by $lh(s)$ we denote its
length. If $s=(s_{1},\ldots,s_{n})\in\mathbb{R}^{n}$ (so $lh(s)=n$) and $k\leq
lh(s)$ then $s|k=(s_{1},\ldots,s_{k})$ is the restriction of $s$ to $k$.

###  2.2 IFS attractors

By $K(X)$ we denote the collection of all compact subsets of a compact metric
space $(X,d)$. Throughout the paper we will assume that $X=[0,1]^{d}$ for some
$d\in\mathbb{N}$. However, the rest of this subsection is true for any compact
$X$.

A function $f\colon X\to X$ is called a contraction on $X$ whenever there
exists a constant $L\in[0,1)$ such that for every $x,y\in X$ it is true that
$d(f(x),f(y))\leqslant L\cdot d(x,y)$.

Every finite set $\\{s_{1},\dots,s_{k}\\}$ of contractions acting on $X$ will
be called an iterated function system or, in short, IFS. By $\mathcal{S}\colon
K(X)\to K(X)$ we denote the Hutchinson operator for $\\{s_{1},\dots,s_{k}\\}$,
i.e.

$\mathcal{S}(A)=\bigcup_{i=1}^{k}s_{i}[A].$

If $(X,d)$ is complete, then so is $(K(X),d_{H})$, where $d_{H}$ is the
Hausdorff metric. Thus, by applying the Banach fixed-point theorem, the
equation $\mathcal{S}(A)=A$ has a unique compact solution. Such set is called
the attractor for the iterated function system $\\{s_{1},\dots,s_{k}\\}$. The
form of the Hutchinson operator justifies why attractors are often used to
describe fractals, since many well known self-similar sets satisfy
$\mathcal{S}(A)=A$ when the contractions comprising $S$ are linear.

By IFSd we will denote the set of all attractors for iterated function systems
acting on $[0,1]^{d}$, i.e., a compact set $A\subseteq[0,1]^{d}$ is in IFSd if
there is an iterated function system acting on $[0,1]^{d}$ such that
$\mathcal{S}(A)=A$.

###  2.3 Weak IFS attractors

A finite set of functions $\\{s_{1},\dots,s_{k}\\}$ acting on $X$ is called a
weak iterated function system, or wIFS, if for each $i\in\\{1,\dots,k\\}$ and
every pair of distinct points $x,y\in X$ it is true that
$d(s_{i}(x),s_{i}(y))<d(x,y)$. The functions themselves will be called weak
contractions. A compact set $A\subseteq X$ satisfying
$A=\bigcup_{i=1}^{k}s_{i}[A]$ is called an attractor for
$\\{s_{1},\dots,s_{k}\\}$. By [4], if $X$ is compact then every weak iterated
function system has a unique attractor.

Obviously, each attractor of some IFS is an attractor of some wIFS. However,
the reverse inclusion is not true – see [7] for counterexamples.

By wIFSd we will denote the set of all attractors for weak iterated function
systems acting on $[0,1]^{d}$, i.e., a compact set $A\subseteq[0,1]^{d}$ is in
wIFSd if there is a weak iterated function system $\\{s_{1},\dots,s_{k}\\}$
acting on $[0,1]^{d}$ such that $A=\bigcup_{i=1}^{k}s_{i}[A]$.

###  2.4 Borel hierarchy

Let $\Gamma$ be a Borel class (for instance $\Gamma=F_{\sigma}$ or
$\Gamma=G_{\delta\sigma}$). We say that a subset $A$ of a Polish space $X$ is
$\Gamma$-hard if for each Polish space $Y$ and each $B\in\Gamma(Y)$ there is a
continuous function $f:Y\to X$ such that $f^{-1}[A]=B$. If additionally
$A\in\Gamma(X)$ then we say that $A$ is $\Gamma$-complete.

$\Gamma$-complete sets can be viewed as the most complicated members of the
class $\Gamma$ – they are in the class $\Gamma$ but not in any lower Borel
class. For instance, a $G_{\delta\sigma}$-complete set cannot be
$F_{\sigma\delta}$.

Observe that if $B\subseteq Y$ is $\Gamma$-complete and there is a continuous
function $f:Y\to X$ such that $f^{-1}[A]=B$ then $A$ is $\Gamma$-hard.

Examples of $\Gamma$-complete sets for various Borel classes $\Gamma$ can be
found in [5]. Such examples, especially the ones with a nice combinatorial
definition, are often applied to show (with the use of the above paragraph)
that some set is $\Gamma$-hard.

One particular example is especially important to us. Treating the power set
$\mathcal{P}(X)$ of a set $X$ as the space $\\{0,1\\}^{X}$ of all functions
$f:X\to\\{0,1\\}$ (equipped with the product topology, where the space
$\left\\{0,1\right\\}$ carries the discrete topology) by identifying subsets
of $X$ with their characteristic functions, allows us to talk about Borel
complexity of subsets of $\mathcal{P}(X)$. The aforementioned example is:

$\emptyset\times\text{Fin}=\left\\{A\subseteq\mathbb{N}^{2}:\forall_{n}A_{n}\text{
is finite}\right\\},$

where $A_{n}=\\{k\in\mathbb{N}:(n,k)\in A\\}$, which is
$F_{\sigma\delta}$-complete (see [8, Corollary 3.4 and discussion below it]).

##  3 Main results

######  Theorem 3.1.

wIFS1 is an analytic subset of $K([0,1])$.

###### Proof.

We will use the following characterization: a set $A\subseteq X$ is analytic
if and only if there exists a Polish space $Y$ and a continuous map $f\colon
Y\to X$ such that $f[Y]=A$ (see [5] or [9]).

Let $L_{n}^{W}$ denote the set of attractors for systems of at most $n$ weak
contractions acting on $[0,1]$. Since $wIFS^{1}=\bigcup_{n}L_{n}^{W}$, it is
sufficient to show that each $L_{n}^{W}$ is analytic and use the fact that the
family of analytic sets is closed under countable unions.

The reasoning will be based on [3]. Specifically, authors define the set

$wLip1(X)=\\{f\in C(X,X)\colon\forall_{x,y\in X,x\neq
y}\>d(f(x),f(y))<d(x,y)\\}$

($C(X,X)$ is the Banach space of all continuous functions from $X$ to $X$
equipped with the supremum norm). In other words, $wLip1(X)$ is the family of
weak contractions acting on $X$. Then the authors consider the Cartesian
product $(wLip1(X))^{n}$ and show that the following function:

$f_{X}\colon(wLip1(X))^{n}\to K(X)$

which maps a set of $n$ weak contractions to its unique attractor, is
continuous provided that $X$ is a compact metric space [3, Lemma 4.6].
Therefore, $f_{[0,1]}[(wLip1([0,1]))^{n}]=L_{n}^{W}$. To finish the proof we
need to make sure that the domain is Polish – and it is in the case of
$X=[0,1]$, as in [3, Remark 4.4 and Lemma 4.5] the authors show that
$wLip1([0,1])$ is a $G_{\delta}$ subset of a closed subset of
$C([0,1],[0,1])$. ∎

The rest of the paper is devoted to showing that wIFSd is
$G_{\delta\sigma}$-hard in $K([0,1]^{d})$, for every $d\in\mathbb{N}$. We will
mostly work in the one-dimensional case, as other cases will follow from it.

In the lemma below the symbols $\exists_{n}^{\infty}$ and
$\forall_{m}^{\infty}$ mean “there exist infinitely many $n$” and “for all $m$
excluding a finite number”, respectively.

######  Lemma 3.2.

The set
$\\{A\subseteq\mathbb{N}^{2}\colon\exists_{n}^{\infty}\>\forall_{m}^{\infty}\>\>(n,m)\in
A\\}$ is $F_{\sigma\delta}$-complete.

###### Proof.

Let us start with the following observation:

$\displaystyle\\{A\subseteq\mathbb{N}^{2}\colon\exists_{n}^{\infty}\>\forall_{m}^{\infty}\>\>(n,m)\in
A\\}=$ $\displaystyle=\>\>$
$\displaystyle\\{A\subseteq\mathbb{N}^{2}\colon\forall_{i}\>\exists_{n\geqslant
i}\>\exists_{j}\>\forall_{m\geqslant j}\>\>(n,m)\in A\\}=$
$\displaystyle=\>\>$ $\displaystyle\bigcap_{i}\bigcup_{n\geqslant
i}\bigcup_{j}\bigcap_{m\geqslant
j}\left\\{A\subseteq\mathbb{N}^{2}\colon(n,m)\in A\right\\}$

and since $\left\\{A\subseteq\mathbb{N}^{2}\colon(n,m)\in A\right\\}$ is a
member of the base of the topology, we automatically obtain that the set in
question is $F_{\sigma\delta}$. It is therefore sufficient to show that it is
$F_{\sigma\delta}$-hard.

For convenience let us denote

$\\{A\colon\exists_{n}^{\infty}\>\forall_{n}^{\infty}\>\>(n,m)\notin
A\\}=\\{A\colon\exists_{n}^{\infty}\>A_{n}\in Fin\\}=Z,$

where $Fin$ denotes the family of all finite subsets of $\mathbb{N}$ and
$A_{n}$ is a vertical section of the set $A$ placed at the $n$th coordinate.

Let us define the following function
$f\colon\mathcal{P}(\mathbb{N}^{2})\to\mathcal{P}(\mathbb{N}^{2})$:

$f(A)=\left\\{(n,m)\in\mathbb{N}^{2}\colon m\in\bigcup_{i\leqslant
n}A_{i}\right\\}.$

We need to show the continuity of the function as well as

$f^{-1}[Z]=\emptyset\times Fin.$

This will finish the proof, since the map $B\mapsto B^{c}$ (mapping a subset
of $\mathbb{N}^{2}$ to its complement) is clearly continuous and $B\in Z$ is
equivalent to
$B^{c}\in\\{A\subseteq\mathbb{N}^{2}\colon\exists_{n}^{\infty}\>\forall_{m}^{\infty}\>\>(n,m)\in
A\\}$.

We will start with the inclusion $f^{-1}[Z]\subseteq\emptyset\times Fin.$ Fix
$B\in f^{-1}[Z]$. Denote $A=f[B]$. Then $A\in Z\cap
f[\mathcal{P}(\mathbb{N}^{2})]$. If there exists $n$ such that $A_{n}\notin
Fin$, then for every $m\geqslant n$ we have $A_{m}\notin Fin$, since $A\in
f[\mathcal{P}(\mathbb{N}^{2})]$. Therefore $A\notin Z$, a contradiction.
Hence, for every $n$ it is true that $A_{n}\in Fin$. If there existed $n$ such
that $B_{n}\notin Fin$, then $\bigcup_{i\leqslant n}B_{i}=A_{n}\notin Fin$. We
obtain $B\in\emptyset\times Fin.$

Let us move to the reverse inclusion. Fix $B\notin f^{-1}[Z]$. Then
$f[B]\notin Z$. Let us denote $A=f[B]$. We have that there exists $n$ such
that $\bigcup_{i\leqslant n}B_{i}=A_{n}\notin Fin$. Therefore there exists
$i\leqslant n$ such that $B_{i}\notin Fin$. Hence, $B\notin\emptyset\times
Fin$.

For the final part we will show the continuity of the function. To do this, we
will show that the preimages of sets from the subbase are open, i.e.

  1. 1.

$f^{-1}[\left\\{A\colon(n,m)\in A\right\\}]$ is open.

  2. 2.

$f^{-1}[\left\\{A\colon(n,m)\notin A\right\\}]$ is open.

For 1. notice the following:

$\displaystyle f^{-1}[\left\\{A\colon(n,m)\in A\right\\}]=$ $\displaystyle=$
$\displaystyle\left\\{B\colon\exists_{i\leqslant n}\>\>(i,m)\in B\right\\}=$
$\displaystyle=$ $\displaystyle\bigcup_{i\leqslant n}\\{B\colon(i,m)\in B\\}$

and the last set is indeed open. Similarly for 2.:

$\displaystyle f^{-1}[\left\\{A\colon(n,m)\notin A\right\\}]=$
$\displaystyle=$ $\displaystyle\left\\{B\colon\forall_{i\leqslant
n}\>\>(i,m)\notin B\right\\}=$ $\displaystyle=$
$\displaystyle\bigcap_{i\leqslant n}\\{B\colon(i,m)\notin B\\}$

and we obtain a finite intersection of open sets, i.e. an open set. ∎

######  Remark 1.

In the proof of Lemma 3.4 we will use a certain modification of the Cantor
ternary set. It is constructed by removing from $[0,1]$ a $(0.1,0.9)$ interval
and leaving two intervals on each side so that each is a tenth of the original
interval. Each next step follows accordingly. We will refer to it as the
“decimal” Cantor set (in contrast to the original ternary Cantor set).
Equivalently, the decimal Cantor set is given by

$\left\\{\sum_{n}x_{n}\cdot\frac{9}{10^{n}}:x_{n}\in\\{0,1\\}\right\\}.$

We will need a certain way of addressing specific elements of this set. We
will describe it now.

Let $s\in\\{0,1\\}^{lh(s)}$ be a finite sequence. Put

$d_{s}=\sum_{1\leqslant k\leqslant lh(s)}e_{lh(s)}^{s|k},$

where $e_{i}^{s|k}$ is the $i$th term of the sequence $e^{s|k}$ and

$e^{s}=\begin{cases}(0,0,\dots)\text{, if $s$ is an empty sequence or a
sequence which ends with 0,}\\\
(0,\dots,0,\frac{9}{10^{lh(s)}}\cdot\frac{1}{2},\frac{9}{10^{lh(s)}}\cdot\frac{1}{4},\dots),\text{
otherwise},\end{cases}$

where in the other case the number of zeros in front is $lh(s)-1$.

We will show the following two properties of such addressing of the decimal
Cantor set:

  * (1)

for each $x\in\\{0,1\\}^{\mathbb{N}}$ we have
$\sum_{n}d_{x|n}=\sum_{k,x(k)=1}\frac{9}{10^{k}}$, which will show that
$\\{\sum_{n}d_{x|n}:x\in\\{0,1\\}^{\mathbb{N}}\\}$ is indeed the decimal
Cantor set,

  * (2)

if $s,t\in\\{0,1\\}^{<\mathbb{N}}$, $s<_{lex}t,lh(s)=lh(t)$ then
$d_{s}<d_{t}$, where $<_{lex}$ is the lexicographic order.

Let us start by showing (1). Fix $x\in\\{0,1\\}^{\mathbb{N}}$.

$\sum_{n}d_{x|n}=\sum_{n}\sum_{k\leqslant
n}e_{n}^{x|k}=\sum_{n}\sum_{k}e_{n}^{x|k}=(*),$

where the last equality holds because $e_{n}^{x|k}=0$ for $k>n$,

$(*)=\sum_{k}\sum_{n}e_{n}^{x|k}=\sum_{k,x(k)=1}\frac{9}{10^{k}},$

because for those $k$ where $x(k)=0$ the sum consists of zeros.

Let us proceed to (2). Let $m$ be the index of the first term where the
sequences $s$ and $t$ differ, i.e. $s|(m-1)=t|(m-1)$ and $s_{m}=0,t_{m}=1$.
Denote $n=lh(s)=lh(t)$.

$d_{t}-d_{s}=\sum_{k<m}e_{n}^{t|k}+e_{n}^{t|m}+\sum_{m<k\leqslant
n}e_{n}^{t|k}-\sum_{k<m}e_{n}^{s|k}-e_{n}^{s|m}-\sum_{m<k\leqslant
n}e_{n}^{s|k}=$ $=e_{n}^{t|m}+\sum_{m<k\leqslant
n}e_{n}^{t|k}-e_{n}^{s|m}-\sum_{m<k\leqslant n}e_{n}^{s|k}\geqslant$
$\geqslant\frac{9}{10^{m}}\cdot\frac{1}{2^{n-m+1}}-\left(\frac{9}{10^{m+1}}\cdot\frac{1}{2^{n-m}}+\frac{9}{10^{m+2}}\cdot\frac{1}{2^{n-m-1}}+\dots+\frac{9}{10^{n}}\cdot\frac{1}{2}\right)=(*),$

where the inequality holds since
$e_{n}^{t|m}=\frac{9}{10^{m}}\cdot\frac{1}{2^{n-m+1}}$ and the content of the
parenthesis covers the extreme case where the difference would be maximal.

We need to show that $(*)>0$. It would be equivalent to:

$\frac{9}{10^{m}}\cdot\frac{1}{2^{n-m+1}}>\frac{9}{10^{m+1}}\cdot\frac{1}{2^{n-m}}+\frac{9}{10^{m+2}}\cdot\frac{1}{2^{n-m-1}}+\dots+\frac{9}{10^{n}}\cdot\frac{1}{2}\iff$
$\frac{1}{2^{n-m+1}}>\frac{1}{10}\cdot\frac{1}{2^{n-m}}+\frac{1}{10^{2}}\cdot\frac{1}{2^{n-m-1}}+\dots+\frac{1}{10^{n-m}}\cdot\frac{1}{2}\iff$
$\frac{1}{2^{n-m+1}}>\sum_{i=1}^{n-m}\left(\frac{1}{2^{n-m}}\cdot\frac{1}{10}\right)\cdot\left(\frac{2}{10}\right)^{i-1}\iff$
$\frac{1}{2^{n-m+1}}>\frac{1}{2^{n-m}}\cdot\frac{1}{10}\cdot\frac{1-\left(\frac{2}{10}\right)^{n-m}}{1-\frac{2}{10}}\iff$
$\frac{1}{2^{n-m+1}}>\frac{1}{2^{n-m}}\cdot\frac{1-\left(\frac{2}{10}\right)^{n-m}}{8}\iff$
$\frac{1}{2^{n-m+1}}>\frac{1}{2^{n-m}}\cdot\frac{1}{8}\cdot\left(\frac{10^{n-m}-2^{n-m}}{10^{n-m}}\right)\iff$
$\frac{1}{2}\cdot 8\cdot 10^{n-m}>10^{n-m}-2^{n-m}\iff$ $3\cdot
10^{n-m}>-2^{n-m}$

and the final inequality is true. This concludes our remark.

######  Remark 2.

In the next lemma we will need the following two technical definitions.

Denote by $D$ the decimal Cantor set (so
$D=\\{\sum_{l}d_{x|l}:x\in\\{0,1\\}^{\mathbb{N}}\\}$) and let
$\alpha\in\\{0,1\\}^{\mathbb{N}}$ and $\delta\in(0,1)$. We define
$g_{\alpha}^{\delta}:D\to[0,1]$ by
$g_{\alpha}^{\delta}(\sum_{l}d_{x|l})=\sum_{l}d_{x|l}\delta^{(1-\alpha_{l})}$
for all $x\in\\{0,1\\}^{\mathbb{N}}$.

Moreover, if $n\in\mathbb{N}$, $X\subseteq\\{0,1\\}^{\mathbb{N}}$ and
$C=\\{\sum_{l}c_{x_{l}}:x\in X\\}$ for some
$\\{c_{s}:s\in\\{0,1\\}^{<\mathbb{N}}\\}\subseteq\mathbb{R}$, then we define:

  * •

$E^{n}_{1}\left(C\right)=\left\\{\sum_{l}c_{x|l}:x\in
X,x_{n+1}=0,x_{n+2}=0\right\\},$

  * •

$E^{n}_{2}\left(C\right)=\left\\{\sum_{l}c_{x|l}:x\in
X,x_{n+1}=0,x_{n+2}=1\right\\},$

  * •

$E^{n}_{3}\left(C\right)=\left\\{\sum_{l}c_{x|l}:x\in
X,x_{n+1}=1,x_{n+2}=0\right\\},$

  * •

$E^{n}_{4}\left(C\right)=\left\\{\sum_{l}c_{x|l}:x\in
X,x_{n+1}=1,x_{n+2}=1\right\\}.$

######  Lemma 3.3.

Suppose that $C=D\cap\left[0,\frac{1}{10^{n}}\right]$ for some
$n\in\mathbb{N}$ (so
$C=\\{\sum_{l}d_{x|l}:x\in\\{0,1\\}^{\mathbb{N}},x_{l}=0\text{ for }l\leq
n\\}$) and fix $\delta\in(\frac{80}{89},1)$, $k\in\mathbb{N}$ and
$\alpha\in\\{0,1\\}^{\mathbb{N}}$ such that $\alpha_{l}=1$ for all $l\geqslant
n+k$. Then for every weak contraction $f$, the set $f[C]$ can intersect at
most two of the sets $E^{n}_{i}(g^{\delta}_{\alpha}[C])$ for $i\leq 4$.
Moreover, $f[C]$ can intersect only two consecutive sets of this form.

###### Proof.

We will prove it inductively with respect to $k$.

In the first step fix $n,\delta,f$ and $\alpha$ such that $\alpha_{l}=1$ for
all $l\geqslant n+1$. Then $g^{\delta}_{\alpha}[C]=C$ (as $d_{x|l}=0$ whenever
$l\leq n$ and $x\in\\{0,1\\}^{\mathbb{N}}$ is such that $x_{m}=0$ for all
$m\leq n$). Therefore either $f[C]\cap(E^{n}_{1}(g^{\delta}_{\alpha}[C])\cup
E^{n}_{2}(g^{\delta}_{\alpha}[C]))=\emptyset$ or
$f[C]\cap(E^{n}_{3}(g^{\delta}_{\alpha}[C])\cup
E^{n}_{4}(g^{\delta}_{\alpha}[C]))=\emptyset$.

Let us proceed to $k=2$, i.e., fix $n,\delta,f$ and $\alpha$ such that
$\alpha_{l}=1$ for all $l\geqslant n+2$. We have two cases. Either
$\alpha_{l}=1$ for all $l\geq n+1$, which has been covered in the previous
paragraph, or $\alpha_{n+1}=0$ and $\alpha_{l}=1$ for all $l\geq n+2$, which
we need to discuss. Denote $C_{L}=C\cap\left[0,\frac{1}{10^{n+1}}\right]$,
$C_{R}=C\cap\left[\frac{9}{10^{n+1}},\frac{1}{10^{n}}\right]$,
$g^{\delta}_{\alpha}[C_{L}]=E^{n}_{1}(g^{\delta}_{\alpha}[C])\cup
E^{n}_{2}(g^{\delta}_{\alpha}[C])$ and
$g^{\delta}_{\alpha}[C_{R}]=E^{n}_{3}(g^{\delta}_{\alpha}[C])\cup
E^{n}_{4}(g^{\delta}_{\alpha}[C])$. Observe that neither $f[C_{L}]$ nor
$f[C_{R}]$ can intersect both $g^{\delta}_{\alpha}[C_{L}]$ and
$g^{\delta}_{\alpha}[C_{R}]$ as the longest gaps in $C_{L}$ and $C_{R}$ have
lengths $\frac{8}{10^{n+2}}$ while the distance between
$g^{\delta}_{\alpha}[C_{L}]$ and $g^{\delta}_{\alpha}[C_{R}]$ is at least
$\delta\frac{8}{10^{n+1}}>\frac{8}{10^{n+2}}$ (as
$\delta>\frac{80}{89}>\frac{1}{10}$). What is more, note that if
$x,y\in\\{0,1\\}^{\mathbb{N}}$ are such that $x_{m}=y_{m}=0$ for all $m\leq n$
and additionally $x|n+1=y|n+1$ (i.e., $x_{n+1}=y_{n+1}$) then

$\sum_{l}d_{x|l}\delta^{(1-\alpha_{l})}-\sum_{l}d_{y|l}\delta^{(1-\alpha_{l})}=\sum_{l}d_{x|l}-\sum_{l}d_{y|l}.$

In other words, $C_{L}$, $C_{R}$, $g^{\delta}_{\alpha}[C_{L}]$ and
$g^{\delta}_{\alpha}[C_{R}]$ all look exactly the same (they are all
translations of $C_{L}$). In particular, $f[C_{L}]$ cannot intersect two sets
of the form $E^{n}_{i}(g^{\delta}_{\alpha}[C])$ for $i\leq 4$ (and neither can
$f[C_{R}]$). Thus, $f[C]$ intersects at most two of them. Observe that the gap
between $C_{L}$ and $C_{R}$ is $\frac{8}{10^{n+1}}$ while the distance between
$E^{n}_{1}(g^{\delta}_{\alpha}[C])$ and $E^{n}_{3}(g^{\delta}_{\alpha}[C])$
(which is the same as the distance between $E^{n}_{2}(g^{\delta}_{\alpha}[C])$
and $E^{n}_{4}(g^{\delta}_{\alpha}[C])$ and smaller than the distance between
$E^{n}_{1}(g^{\delta}_{\alpha}[C])$ and $E^{n}_{4}(g^{\delta}_{\alpha}[C])$)
is at least $\delta\left(\frac{8}{10^{n+1}}+\frac{9}{10^{n+2}}\right)$. Since
$\delta>\frac{80}{89}$, we have

$\frac{8}{10^{n+1}}<\delta\left(\frac{8}{10^{n+1}}+\frac{9}{10^{n+2}}\right).$

This means that $f[C]$ can only intersect two consecutive sets of the form
$E^{n}_{i}(g^{\delta}_{\alpha}[C])$ for $i\leq 4$.

Now we move to the inductive step. Suppose that the thesis is true for some
$k$. Again fix $n,\delta,f$ and $\alpha$ such that $\alpha_{l}=1$ for all
$l\geqslant n+k+1$. Let $C_{L}$ and $C_{R}$ be as before. Assume to the
contrary that $f[C_{L}]\cup f[C_{R}]$ intersects at least three sets of the
form $E^{n}_{i}(g^{\delta}_{\alpha}[C])$ for $i\leq 4$. Then either $f[C_{L}]$
or $f[C_{R}]$ intersect at least two of them. Without loss of generality we
may assume that $f[C_{L}]$ has this property. Observe that $f[C_{L}]$ cannot
intersect both $L=E^{n}_{1}(g^{\delta}_{\alpha}[C])\cup
E^{n}_{2}(g^{\delta}_{\alpha}[C])$ and
$R=E^{n}_{3}(g^{\delta}_{\alpha}[C])\cup E^{n}_{4}(g^{\delta}_{\alpha}[C])$
for the same reason as before (as $\delta>\frac{80}{89}>\frac{1}{10}$). Thus,
without loss of generality we may assume that $C_{L}\subseteq L$. It follows
from the inductive assumption that $C_{L}$ can only intersect two consecutive
sets of the form $E^{n+1}_{i}(L)$ for $i\leq 4$ (note that
$E^{n}_{1}(g^{\delta}_{\alpha}[C])=E^{n+1}_{1}(L)\cup E^{n+1}_{2}(L)$ and
$E^{n}_{2}(g^{\delta}_{\alpha}[C])=E^{n+1}_{3}(L)\cup E^{n+1}_{4}(L)$). Hence,
if $f[C_{L}]$ intersects two sets of the form
$E^{n}_{i}(g^{\delta}_{\alpha}[C])$, then it has to intersect $E^{n+1}_{2}(L)$
and $E^{n+1}_{3}(L)$. Then $f[C_{R}]$ cannot intersect $R$ as the distance
between $E^{n+1}_{3}(L)$ and $R$ is at least
$\delta\left(\frac{8}{10^{n+1}}+\frac{9}{10^{n+2}}\right)$ while the gap
between $C_{L}$ and $C_{R}$ is $\frac{8}{10^{n+1}}$ and
$\delta>\frac{80}{89}$. This finishes the proof. ∎

Now we move to the most technical part from which $G_{\delta\sigma}$-hardness
of wIFSd will easily follow.

######  Lemma 3.4.

There is a continuous function $\varphi\colon\mathcal{P}(\mathbb{N}^{2})\to
K([0,1])$ such that
$\varphi^{-1}[wIFS^{1}]=\mathcal{P}(\mathbb{N}^{2})\setminus\\{A\colon\exists_{n}^{\infty}\>\forall_{m}^{\infty}\>\>(n,m)\in
A\\}$. In particular, wIFS1 is $G_{\delta\sigma}$-hard in $K([0,1])$.

###### Proof.

The “In particular” part follows from Lemma 3.2.

In this proof for $A\subseteq\mathbb{R}$ and $r\in\mathbb{R}$ we will write
$rA=\\{r\cdot a:a\in A\\}$ and $A+r=\\{a+r:a\in A\\}$.

We will start by defining a sequence $(a_{n})_{n}$ which we will need later.
Put $a_{0}=1.9$. Let $C_{0}$ be the decimal Cantor set (see Remark 1).

Put $a_{1}^{\prime}=\frac{a_{0}}{2}$ and $\varepsilon_{1}=\frac{1}{5}\cdot
a_{1}^{\prime}$.

Let us introduce a notation such that our decimal Cantor set

$C_{0}=\bigcap_{i}\bigcup_{j\leqslant k_{i}^{1}}I_{i}^{j},$

where $I_{i}^{j}$ are the intervals from the construction of decimal Cantor
set: $I_{i}^{1}=[0,1/10^{i-1}]$ and $|I_{i}^{j_{1}}|=|I_{i}^{j_{2}}|$ for all
$i\in\mathbb{N}$ and $j_{1},j_{2}\leq k_{i}^{1}$ (in particular,
$k_{i}^{1}=2^{i-1}$).

Since $C_{0}$ is a measure zero set, there exists $i_{1}$ such that

$1.9\cdot\sum_{j\leqslant k_{i_{1}}^{1}}|I_{i_{1}}^{j}|=|I_{i_{1}}^{1}|\cdot
k_{i_{1}}^{1}\cdot 1.9<\varepsilon_{1}.$

To shorten the notation we will write
$\widetilde{k_{i_{1}}^{1}}=k_{i_{1}}^{1}\cdot 5$.

Pick $\delta_{1}\in(0,1)$ such that
$\delta_{1}^{\widetilde{k^{1}_{i_{1}}}-1}>\frac{190}{199}$.

Denote $D_{1}=C_{0}\cap I_{i_{1}}^{1},C_{1}^{1}=D_{1}+a_{0}$ and

$C_{1}^{k}=\delta_{1}^{k-1}\cdot D_{1}+\left(a_{0}+|I_{i_{1}}^{1}|\cdot
1.9\cdot(1+\delta_{1}+\delta_{1}^{2}+\dots+\delta_{1}^{k-2})\right)$

for $k\in\\{2,\dots,\widetilde{k_{i_{1}}^{1}}\\}$.

Put $a_{1}=|I_{i_{1}}^{1}|\cdot
1.9\cdot\left(1+\delta_{1}+\dots+\delta_{1}^{\widetilde{k_{i_{1}}^{1}}-1}\right)$.
Therefore we obtain

$a_{1}<|I_{i_{1}}^{1}|\cdot
1.9\cdot\widetilde{k_{i_{1}}^{1}}=|I_{i_{1}}^{1}|\cdot 1.9\cdot
k_{i_{1}}^{1}\cdot 5<5\varepsilon_{1}=a_{1}^{\prime}=\frac{1}{2}a_{0}.$

Hence, $a_{1}\leqslant\frac{1}{2}a_{0}.$

Let us assume that $a_{n}$ is already defined. Put
$a_{n+1}^{\prime}=\frac{a_{n}}{2}$ and
$\varepsilon_{n+1}=\frac{1}{5(n+1)}\cdot a_{n+1}^{\prime}$.

Consider the previously defined sets $C_{l}^{j}$ for $l\leq n$ and
$j\leq\widetilde{k_{i_{l}}^{l}}$. For each such set let us divide its length
by $\delta_{l}^{j-1}$ and shift it so that its middle coincides with the
middle of $C_{l}^{j}$. Let us denote the rescaled and shifted set $E_{l}^{j}$.
Notice that each $E_{1}^{j}$ is a translation of the set $D_{1}=C_{0}\cap
I_{i_{1}}^{1}$ (in particular, the diameter of each $E_{1}^{j}$ is
$\frac{1}{10^{i_{1}-1}}$). From the next paragraphs of the construction it
will follow that in fact each $E_{l}^{j}$ is a translation of $C_{0}\cap
I_{i}^{1}$ for some $i\in\mathbb{N}$.

Put

$C_{n}=C_{0}\cup\bigcup_{k\leqslant\widetilde{k_{i_{1}}^{1}}}E_{1}^{k}\cup\dots\cup\bigcup_{k\leqslant\widetilde{k_{i_{n}}^{n}}}E_{n}^{k}=C_{n-1}\cup\bigcup_{k\leqslant\widetilde{k_{i_{n}}^{n}}}E_{n}^{k}.$

Let $\left(I_{i}^{j}\right)$ be such a sequence of intervals that

$C_{n}=\bigcup_{i}\bigcap_{j\leqslant k_{i}^{n+1}}I_{i}^{j},$

$|I_{i}^{j}|=|I_{i}^{j^{\prime}}|$ and $I_{i}^{1}=[0,1/10^{i-1}]$ for all
$i\in\mathbb{N}$ and $j_{1},j_{2}\leq k_{i}^{1}$.

Since $C_{n}$ is a finite union of subsets of the decimal Cantor set, it is of
measure zero. Therefore there exists $i_{n+1}$ such that

$1.9\cdot\sum_{j\leqslant
k_{i_{n+1}}^{n+1}}|I_{i_{n+1}}^{j}|=|I_{i_{n+1}}^{1}|\cdot
k_{i_{n+1}}^{n+1}\cdot 1.9<\varepsilon_{n+1}.$

Put $\widetilde{k_{i_{n+1}}^{n+1}}=k_{i_{n+1}}^{n+1}\cdot 5\cdot(n+1)$ and
$D_{n+1}=C_{0}\cap I_{i_{n+1}}^{1}$. Pick $\delta_{n+1}\in(0,1)$ such that
$\delta_{n+1}^{\widetilde{k^{n+1}_{i_{n+1}}}-1}>\frac{190}{199}$.

Let us put

$C_{n+1}^{1}=D_{n+1}+(a_{0}+\dots+a_{n}),$
$C_{n+1}^{k}=\delta_{n+1}^{k-1}\cdot
D_{n+1}+\left(a_{0}+\dots+a_{n}+|I_{i_{n+1}}^{1}|\cdot
1.9\cdot(1+\delta_{n+1}+\delta_{n+1}^{2}+\dots+\delta_{n+1}^{k-2})\right)$

for $k\in\left\\{2,\dots,\widetilde{k_{i_{n+1}}^{n+1}}\right\\}$. Observe that
sets $C_{l}^{j}$ defined in this way guarantee that in the next inductive step
each $E_{n+1}^{j}$ (defined similarly as in the paragraph before the
definition of $C_{n}$) is a translation of $C_{0}\cap I_{i_{n+1}}^{1}$. Hence,
$C_{n+1}$ will have measure zero.

Finally, put

$a_{n+1}=|I_{i_{n+1}}^{1}|\cdot
1.9\cdot\left(1+\delta_{n+1}+\cdots+\delta_{n+1}^{\widetilde{k_{i_{n+1}}^{n+1}}-1}\right).$

Similarly as before, it turns out that $a_{n+1}\leqslant\frac{a_{n}}{2}$,
which concludes the inductive construction.

Since $a_{n+1}\leqslant\frac{a_{n}}{2}$ for all $n$, the series
$\sum_{i=0}^{\infty}a_{n}\leq
a_{0}\cdot\sum_{i=0}^{\infty}\frac{1}{2^{i}}<+\infty$, which implies that
there exists $x$ such that

$\overline{C_{0}\cup\bigcup_{n}\bigcup_{k\leqslant\widetilde{k_{i_{n}}^{n}}}C_{n}^{k}}=C_{0}\cup\bigcup_{n}\bigcup_{k\leqslant\widetilde{k_{i_{n}}^{n}}}C_{n}^{k}\cup\\{x\\}.$

where the upper dash denotes the closure operator.

Let us define $\psi\colon\mathbb{R}\to\mathbb{R}$ as $\psi(y)=\frac{y}{x}$,
i.e. it is the scaling of the entire construction into the interval $[0,1]$.

We are ready to introduce the required map
$\varphi\colon\mathcal{P}(\mathbb{N}^{2})\to K([0,1]).$ First, let us define
it on extreme arguments.

$\varphi(\emptyset)=\psi\left(C_{0}\cup\bigcup_{n}\bigcup_{k\leqslant\widetilde{k_{i_{n}}^{n}}}C_{n}^{k}\cup\\{x\\}\right),$
$\varphi(\mathbb{N}^{2})=\psi\left(C_{0}\cup\bigcup_{n}\bigcup_{k\leqslant\widetilde{k_{i_{n}}^{n}}}E_{n}^{k}\cup\\{x\\}\right).$

Now let us define $\varphi$ for any set $A\subseteq\mathbb{N}^{2}$. We will
use auxiliary functions
$\tau_{n}\colon\mathcal{P}(\mathbb{N}^{2})\to\\{0,1\\}^{\mathbb{N}}$ such that
$\tau_{n}(A)=(j_{1},j_{2},\dots)$ where $j_{i}=1$ if $(n,i)\in A$ and
$j_{i}=0$ otherwise. Let us go back to Remark 1: there exists a set
$\\{d_{s}\colon s\in\\{0,1\\}^{<\mathbb{N}}\\}$ such that
$D_{n}=\left\\{\sum_{i}d_{x|i}\colon x\in\\{0,1\\}^{\mathbb{N}},x_{i}=0\text{
for }i\leq i_{n}-1\right\\}$. Then define

$C_{n}^{j}(A)=\left\\{\sum_{l}d_{x|l}\cdot\delta^{(j-1)(1-\tau_{n}(A)(l))}\colon
x\in\\{0,1\\}^{\mathbb{N}},x_{i}=0\text{ for }i\leq i_{n}-1\right\\},$

where $\tau_{n}(A)(l)$ denotes the $l$th term of $\tau_{n}(A)$, and finally
shift $C_{n}^{j}(A)$ so that its midpoint coincides with the midpoint of
$C_{n}^{j}$. Equivalently, using the notation from Remark 2,
$C_{n}^{j}(A)=g^{\delta^{(j-1)}}_{\tau_{n}(A)}(C_{0}\cap I^{1}_{i_{n}})$.
Having all of those, put

$\varphi(A)=\psi\left(C_{0}\cup\bigcup_{n}\bigcup_{k\leqslant\widetilde{k_{i_{n}}^{n}}}C_{n}^{k}(A)\cup\\{x\\}\right).$

Notice that this definition is consistent with the previously defined values
at $\emptyset$ and $\mathbb{N}^{2}$.

Observe that the set $C_{n}^{j}(A)$ is an attractor of some IFS, for each $A$,
$n$ and $j$. Indeed, without loss of generality we can assume that
$C_{n}^{j}(A)\subseteq[0,1]$ (since a shift of an IFS attractor is still an
IFS attractor). Given $x\in\\{0,1\\}^{\mathbb{N}}$ such that $x_{i}=0$ for
$i\leq i_{n}-1$ let $\hat{x}^{0},\hat{x}^{1}\in\\{0,1\\}^{\mathbb{N}}$ be
given by:

  * •

$\hat{x}^{0}_{i}=\hat{x}^{1}_{i}=0$ for $i\leq i_{n}-1$,

  * •

$\hat{x}^{0}_{i_{n}}=0$,

  * •

$\hat{x}^{1}_{i_{n}}=1$,

  * •

$\hat{x}^{0}_{i}=\hat{x}^{1}_{i}=x_{i-1}$ for $i>i_{n}$.

Let also $f_{1},f_{2}:[0,1]\to[0,1]$ be functions such that:

  * •

$f_{1}(\sum_{l}d_{x|l}\cdot\delta^{(j-1)(1-\tau_{n}(A)(l))})=\sum_{l}d_{\hat{x}^{0}|l}\cdot\delta^{(j-1)(1-\tau_{n}(A)(l))}$
for all $x\in\\{0,1\\}^{\mathbb{N}}$ such that $x_{i}=0$ for $i\leq i_{n}-1$,

  * •

$f_{2}(\sum_{l}d_{x|l}\cdot\delta^{(j-1)(1-\tau_{n}(A)(l))})=\sum_{l}d_{\hat{x}^{1}|l}\cdot\delta^{(j-1)(1-\tau_{n}(A)(l))}$
for all $x\in\\{0,1\\}^{\mathbb{N}}$ such that $x_{i}=0$ for $i\leq i_{n}-1$,

  * •

$f_{1}[[0,\min C_{n}^{j}(A)]]=f_{1}(\min C_{n}^{j}(A))$,

  * •

$f_{2}[[0,\min C_{n}^{j}(A)]]=f_{2}(\min C_{n}^{j}(A))$,

  * •

$f_{1}[[\max C_{n}^{j}(A),1]]=f_{1}(\max C_{n}^{j}(A))$,

  * •

$f_{2}[[\max C_{n}^{j}(A),1]]=f_{1}(\max C_{n}^{j}(A))$,

  * •

both $f_{1}$ and $f_{2}$ are linear on every open interval disjoint with
$C_{n}^{j}(A)\cup[0,\min C_{n}^{j}(A)]\cup[\max C_{n}^{j}(A),1]$.

From the above conditions it is obvious that
$C_{n}^{j}(A)=f_{1}[C_{n}^{j}(A)]\cup f_{2}[C_{n}^{j}(A)]$. Observe also that
both $f_{1}$ and $f_{2}$ are non-decreasing. We will show that both $f_{1}$
and $f_{2}$ are contractions. Note that actually from the last five items
above it suffices to show that if $v,w\in C_{n}^{j}(A)$ then
$|f_{1}(v)-f_{1}(w)|\leq\frac{1}{5}|v-w|$ and
$|f_{2}(v)-f_{2}(w)|\leq\frac{1}{5}|v-w|$. Fix any
$x,y\in\\{0,1\\}^{\mathbb{N}}$, $x\neq y$, such that $x_{i}=y_{i}=0$ for
$i\leq i_{n}-1$. Without loss of generality we may assume that $y<_{lex}x$.
Then also $\hat{y}^{0}|l\leq_{lex}\hat{x}^{0}|l$ and
$\hat{y}^{1}|l\leq_{lex}\hat{x}^{1}|l$ for every $l$. Recall that for each
$z\in\\{0,1\\}^{\mathbb{N}}$ we have
$\sum_{n}d_{z|n}=\sum_{k,z_{k}=1}\frac{9}{10^{k}}$ and if
$s,t\in\\{0,1\\}^{<\mathbb{N}}$, $s<_{lex}t,lh(s)=lh(t)$ then $d_{s}<d_{t}$
(see Remark 1). Thus we have $f_{1}(x)>f_{1}(y)$ and:

$|f_{1}(x)-f_{1}(y)|=f_{1}(x)-f_{1}(y)=\sum_{l}\left(d_{\hat{x}^{0}|l}-d_{\hat{y}^{0}|l}\right)\cdot\delta^{(j-1)(1-\tau_{n}(A)(l))}\leq$
$\sum_{l}\left(d_{\hat{x}^{0}|l}-d_{\hat{y}^{0}|l}\right)=\sum_{k,\hat{x}^{0}_{k}=1}\frac{9}{10^{k}}-\sum_{k,\hat{y}^{0}_{k}=1}\frac{9}{10^{k}}=\frac{1}{10}\left(\sum_{k,x_{k}=1}\frac{9}{10^{k}}-\sum_{k,y_{k}=1}\frac{9}{10^{k}}\right)\leq$
$\frac{1}{5}\delta^{j-1}\left(\sum_{k,x_{k}=1}\frac{9}{10^{k}}-\sum_{k,y_{k}=1}\frac{9}{10^{k}}\right)=\frac{1}{5}\delta^{j-1}\left(\sum_{l}d_{x|l}-\sum_{l}d_{y|l}\right)\leq$
$\frac{1}{5}\left(\sum_{l}d_{x|l}\cdot\delta^{(j-1)(1-\tau_{n}(A)(l))}-\sum_{l}d_{y|l}\cdot\delta^{(j-1)(1-\tau_{n}(A)(l))}\right).$

This shows that $f_{1}$ is a contraction. For $f_{2}$ the reasoning is
similar.

In the following for a fixed $A\subseteq\mathbb{N}^{2}$ we will refer to
$\bigcup_{k\leqslant\widetilde{k_{i_{n}}^{n}}}C_{n}^{k}(A)$ or to
$\psi\left(\bigcup_{k\leqslant\widetilde{k_{i_{n}}^{n}}}C_{n}^{k}(A)\right)$
as the $n$th section and to single $C_{n}^{k}(A)$ or $\psi(C_{n}^{k}(A))$ as
member of the $n$th section.

Before presenting the remaining part of the proof, we would like to examine
some conditions imposed on $\delta_{n}$ which follow from our construction.

  * (1)

$\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}>\frac{80}{89}$

(so we can apply Lemma 3.3),

  * (2)

$|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-2}\cdot
0.9>|I_{i_{n}}^{1}|-|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}.$

  * (2’)

$|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}\cdot
0.9>\frac{1}{2}\cdot\left(|I_{i_{n}}^{1}|-|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}\right).$

The meaning behind condition (2) is the following: members of the $n$th
section will not overlap even in the case of a maximal expansion. Indeed, the
gap between the last two members of a section (which is always the smallest
gap in a section), if they are maximally contracted, is of the same size as
the left-hand side of the inequality, while the right-hand side of the
inequality is an upper bound for the difference between lengths of that gap in
cases of maximal contraction and maximal expansion:

$\frac{1}{2}\cdot\left(|I_{i_{n}}^{1}|-|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-2}\right)+\frac{1}{2}\cdot\left(|I_{i_{n}}^{1}|-|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}\right)<|I_{i_{n}}^{1}|-|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}.$

Similarly, condition (2’) is introduced in order to assure that sections do
not overlap. Let us notice that condition (1) implies (2) and (2’), i.e.:

$(1)\implies\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}>\frac{10}{19}\implies(2).$
$(1)\implies\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}>\frac{10}{29}\implies(2^{\prime}).$

  * (3)

$|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-2}\cdot
0.9-\left(|I_{i_{n}}^{1}|-|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}\right)>\frac{8}{10}\cdot|I_{i_{n}}^{1}|.$

  * (3’)

$|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}\cdot
0.9-\frac{1}{2}\cdot\left(|I_{i_{n}}^{1}|-|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}\right)>\frac{8}{10}\cdot|I_{i_{n}}^{1}|.$

Similarly as before, the left-hand side of (3’) is the length of a gap behind
a section in the case of maximal expansion, while the right-hand side is the
gap in the first Cantor section from the left (i.e. the longest one). From
this condition the image under any weak contraction of the longest member of
the $n$th section will not overlap with two sections on the right at once (and
therefore neither will any other member of the $n$th section). In (3) the
left-hand side is a lower bound for the gap between members of the $n$th
section. Thus, (3) assures us that the image under any weak contraction of any
member of the $n$th section will not overlap with two members of this section.
Let us notice the following:

$(3^{\prime})\iff\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}>\frac{13}{14},$
$\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}>\frac{18}{19}\implies(3).$

  * (4)

$\displaystyle|I_{i_{n}}^{1}|\cdot
0.9<|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-2}\cdot 0.9$
$\displaystyle-\left(|I_{i_{n}}^{1}|-|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}\right)+$
$\displaystyle+|I_{i_{n}}^{1}|\cdot
0.09\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}.$

Now the left-hand side is the maximal distance between two members of the
$n$th section. The right-hand side is a bound for the minimal distance between
two members of the $n$th section plus the
$|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}\cdot 0.09$
factor. Following condition (1) and Lemma 3.3, the image of any member
$C_{n}^{j}(A)$ of the $n$th section under a weak contraction can intersect at
most two consecutive sets of the form $E^{i_{n}}_{i}(C_{n}^{j^{\prime}}(A))$
for $i\leq 4$ (see Remark 2 for the definition of those sets). The minimal
distance between $\min C_{n}^{j^{\prime}}(A)$ and
$E^{i_{n}}_{2}(C_{n}^{j^{\prime}}(A))$ (as well as between $\max
C_{n}^{j^{\prime}}(A)$ and $E^{i_{n}}_{3}(C_{n}^{j^{\prime}}(A))$) is at least
$|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}\cdot 0.09$.
Therefore, condition (4) (together with (3)) guarantees that for any weak
contraction $f$ such that $f[\varphi(A)]\subseteq\varphi(A)$ and
$f[C_{n}^{j}(A)]\subseteq C_{n}^{j^{\prime}}(A)$, either $f[C_{n}^{j}(A)]$ is
a subset of the left-hand half of $C_{n}^{j^{\prime}}(A)$ or
$f[C_{n}^{j-1}(A)]\cup f[C_{n}^{j+1}(A)]\subseteq C_{n}^{j^{\prime}}(A)\cup
C_{n}^{j^{\prime}+1}(A)$. Similarly, either $f[C_{n}^{j}(A)]$ is a subset of
the right-hand half of $C_{n}^{j^{\prime}}(A)$ or $f[C_{n}^{j-1}(A)]\cup
f[C_{n}^{j+1}(A)]\subseteq C_{n}^{j^{\prime}}(A)\cup C_{n}^{j^{\prime}-1}(A)$.
Let us notice the following.

$\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}>\frac{190}{199}\implies(4).$

  * (4’)

$|I_{i_{n}}^{1}|\cdot
0.9<|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}\cdot
0.9-\frac{1}{2}\cdot\left(|I_{i_{n}}^{1}|-|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}\right)+|I_{i_{n}}^{1}|\cdot\delta_{n}^{\widetilde{k_{i_{n}}^{n}}-1}\cdot
0.09.$

Condition (4’) is analogous to (4), but instead of considering the minimal
distance between two members of the $n$th section we take the minimal gap
behind the $n$th section. After computations it turns out that

$(4^{\prime})\iff\delta_{n}^{\widetilde{k_{i_{n}}^{1}}-1}>\frac{140}{149}.$

Now we continue our proof. We will show that $\varphi$ is continuous. Fix any
$A\subseteq\mathbb{N}^{2}$ and $r\in(0,1)$. Note that
$\\{B\subseteq\mathbb{N}^{2}:A\cap F=B\cap F\\}$ is open in
$\mathcal{P}(\mathbb{N}^{2})$, for every finite set
$F\subseteq\mathbb{N}^{2}$. Thus, we wish to find a finite set
$F\subseteq\mathbb{N}^{2}$ such that $B\cap F=A\cap F$ implies $\varphi(B)\in
B(\varphi(A),r)$, where $B(\varphi(A),r)$ denotes the ball in $K([0,1])$ of
radius $r$ and centered at $\varphi(A)$. Since
$\lim_{n\to\infty}\sum_{i>n}a_{i}=0$, there is $m\in\mathbb{N}$ such that
$\varphi(B)\in B(\varphi(A),r)$ whenever
$A\cap(\\{1,\ldots,m\\}\times\mathbb{N})=B\cap(\\{1,\ldots,m\\}\times\mathbb{N})$.
Also, for any $x\in\\{0,1\\}^{\mathbb{N}}$ the series $\sum_{n}d_{x|n}$ is
convergent. Therefore for any $n<m$ only the initial interval of $\tau_{n}(A)$
matters. This shows that $\varphi$ is continuous.

If $A\subseteq\mathbb{N}^{2}$ is such that

$\forall_{n}^{\infty}\>\exists_{m}^{\infty}\>(n,m)\notin A,\qquad(*)$

then we would like to obtain that $\varphi(A)\in wIFS^{1}$. The sentence $(*)$
means that
$\exists_{n_{0}}\>\forall_{n>n_{0}}\>\exists_{m}^{\infty}\>(n,m)\notin A$. Let
us denote the union of first $n_{0}$ sections and $\psi(C_{0})$ by $B$, i.e.:

$B=\psi\left(C_{0}\cup\bigcup_{n\leqslant
n_{0}}\bigcup_{k\leqslant\widetilde{k_{i_{n}}^{n}}}C_{n}^{k}(A)\right).$

The set $B$ is a union of $\psi(C_{0})$ (which is an attractor for the
contractions $f_{1}(x)=\psi(\frac{x}{10})$ and
$f_{2}(x)=\psi(\frac{x}{10}+\frac{9}{10})$) and finitely many pairwise
disjoint sets of the form $\psi(C_{n}^{k}(A))$. Since each $C_{n}^{k}(A)$ is
an attractor for some IFS, so is each $\psi(C_{n}^{k}(A))$. We can
additionally require that each of those contractions sends
$[0,\min\psi(C_{n}^{k}(A)))$ on the same point as $\min\psi(C_{n}^{k}(A))$ and
$(\max\psi(C_{n}^{k}(A)),1]$ on the same point as $\max\psi(C_{n}^{k}(A))$.
Therefore there exists $k$ and an iterated function system
$\\{f_{1},f_{2},\dots,f_{k}\\}$ (consisting of regular contractions), such
that $B=\bigcup_{i\leqslant k}f_{i}[B]$. Without the loss of generality
$\bigcup_{i\leqslant k}f_{i}[\varphi(A)]\subseteq B$ (it suffices to require
that $f_{i}[\varphi(A)\setminus B]=f_{i}(\max B)$ for all $i\leq k$).

Let $f$ be such that the following conditions hold:

  * 1.

$f(1)=\psi(x)=1,$

  * 2.

$\forall_{n\geqslant
n_{0}}\>f\left[C_{n}^{\widetilde{k_{i_{n}}^{n}}}\right]=C_{n+1}^{1}$,

  * 3.

$\forall_{n>n_{0}}\>\forall_{j<\widetilde{k_{i_{n}}^{n}}}f\left[C_{n}^{j}\right]=C_{n}^{j+1}$,

  * 4.

$f\left[0,\min\psi\left(C_{n_{0}}^{k_{i_{n_{0}}}^{n_{0}}}\right)\right]=\min\psi\left(C_{n_{0}}^{k_{i_{n_{0}}}^{n_{0}}}\right)$,

  * 5.

$f$ is a weak contraction.

Then we would have $\varphi(A)=f\left[\varphi(A)\right]\cup\bigcup_{i\leqslant
k}f_{i}\left[\varphi(A)\right]$. Why is it possible to pick such $f$? In fact
only item 3. is problematic as it could contradict item 5. Now we will show
that this is not a problem.

Let $n>n_{0}$ and $j<\widetilde{k_{i_{n}}^{n}}$. Also, fix
$x,y\in\\{0,1\\}^{\mathbb{N}},x>_{lex}y$. There exists $k$ such that $x|k\neq
y|k$. Additionally, there exists $m>k$ such that $(n,m)\notin A$ (since
$n>n_{0}$). Therefore $\tau_{n}(A)(m)=0.$ Then

$\sum_{l}d_{x|l}\cdot\delta^{(j-1)\cdot(1-\tau_{n}(A)(l))}-\sum_{l}d_{y|l}\cdot\delta^{(j-1)\cdot(1-\tau_{n}(A)(l))}=$
$=\sum_{l}\left(d_{x|l}-d_{y|l}\right)\cdot\delta^{(j-1)\cdot(1-\tau_{n}(A)(l))}=$
$=\sum_{l\neq
m}\left(d_{x|l}-d_{y|l}\right)\cdot\delta^{(j-1)\cdot(1-\tau_{n}(A)(l))}+\left(d_{x|m}-d_{y|m}\right)\cdot\delta^{(j-1)}\geqslant$
$\geqslant\sum_{l\neq
m}\left(d_{x|l}-d_{y|l}\right)\cdot\delta^{j\cdot(1-\tau_{n}(A)(l))}+\left(d_{x|m}-d_{y|m}\right)\cdot\delta^{(j-1)}>$
$>\sum_{l\neq
m}\left(d_{x|l}-d_{y|l}\right)\cdot\delta^{j\cdot(1-\tau_{n}(A)(l))}+\left(d_{x|m}-d_{y|m}\right)\cdot\delta^{j}.$

(the last inequality is true as $d_{x|m}-d_{y|m}>0$ by $x>_{lex}y$ – see
Remark 1). This part is concluded.

The following is left to be shown:

$\forall_{A\subseteq\mathbb{N}^{2}}\>\exists_{n}^{\infty}\>\forall_{m}^{\infty}\>\>(n,m)\in
A\implies\varphi(A)\notin wIFS^{1}.$

Let us fix $A\subseteq\mathbb{N}^{2}$ such that
$\exists_{n}^{\infty}\>\forall_{m}^{\infty}\>\>(n,m)\in A$ and assume
otherwise: that $\varphi(A)$ is an attractor for a system of $k$ weak
contractions $f_{1},f_{2},\dots,f_{k}$. Let us define the following sequences
of sets:

$K_{n}=\psi\left(\bigcup_{l\leqslant\widetilde{k_{i_{n}}^{n}}}C_{n}^{l}(A)\right),$
$L_{n}=\varphi(A)\cap[0,\min K_{n}),$ $R_{n}=\varphi(A)\cap(\max K_{n},1],$

(so $K_{n}$ is the $n$th section).

Observation 1. For any $j>k$ the set $\bigcup_{i\leqslant k}f_{i}[L_{j}]$
intersects at most a fifth of all $\psi\left(C_{j}^{l}(A)\right)$. It follows
from the fact that

$\widetilde{k_{i_{j}}^{j}}=k_{i_{j}}^{j}\cdot 5\cdot j>k_{i_{j}}^{j}\cdot
5\cdot k$

and $L_{j}$ consists of $k_{i_{j}}^{j}$ Cantor sets longer than
$\psi\left(C_{j}^{l}(A)\right)$ (the same amount for every
$l\leqslant\widetilde{k_{i_{j}}^{j}}$) each of which cannot overlap two
members of $j$th section (by (3’)).

Observation 2. If $f_{i}\left[R_{j}\right]\cap K_{j}\neq\emptyset$ for some
$i\leq k$ and $j\in\mathbb{N}$, then the whole set $f_{i}\left[R_{j}\right]$
is a subset of one member of $j$th section. This follows from the fact that
each $R_{j}$ has gaps between its members which are smaller than the smallest
gap between members of $j$th section.

Observation 3. If for some $i\leq k$ there is $j\in\mathbb{N}$ such that
$f_{i}\left[K_{j}\right]\subseteq K_{j}\cup L_{j}$, then $f_{i}\left[K_{j}\cup
R_{j}\right]\subseteq K_{j}\cup L_{j}$.

By Observation 3., it is impossible that for every $i\leqslant k$ there exists
$j_{i}$ such that $f_{i}\left[K_{j_{i}}\right]\subseteq K_{j_{i}}\cup
L_{j_{i}}$. Indeed, otherwise for $n>k,j_{1},\dots,j_{k}$ the set $K_{n}$
would not be entirely covered (by Observation 1.), since in this case

$K_{n}\cap\bigcup_{i\leq k}f_{i}[\varphi(A)]=K_{n}\cap\bigcup_{i\leq
k}f_{i}[L_{n}].$

Let us pick $n>k$ such that $\forall_{m}^{\infty}\>(n,m)\in A$ and for every
$i\leqslant k$ if there exists such $j_{i}$ that
$f_{i}\left[K_{j_{i}}\right]\subseteq K_{j_{i}}\cup L_{j_{i}}$, then
$n>j_{i}$. If no such $j_{i}$ exists, then instead pick any $n>k$ such that
simply $\forall_{m}^{\infty}\>(n,m)\in A$. We also require for $n$ to be
sufficiently large that

$\widetilde{k_{i_{n}}^{n}}>\lceil\frac{1}{2}\widetilde{k_{i_{n}}^{n}}\rceil+\lceil\frac{1}{5}\widetilde{k_{i_{n}}^{n}}\rceil+k.$

Since $\widetilde{k}\to\infty$, finding such $n$ is possible.

We will show that $K_{n}$ cannot be covered by $\bigcup_{i\leq
k}f_{i}[\varphi(A)]$. Let us notice that the set $\bigcup_{i\leqslant
k}f_{i}[L_{n}]$ intersects at most a fifth of the members of $K_{n}$
(Observation 1.). Since for each $i$ the set $f_{i}[R_{n}]$ intersects at most
one member of $K_{n}$ (Observation 2.), the union $\bigcup_{i\leqslant
k}f_{i}[R_{n}]$ covers at most $k$ of them. Thus, there are still

$\widetilde{k_{i_{n}}^{n}}-\lceil\frac{1}{5}\widetilde{k_{i_{n}}^{n}}\rceil-k>\lceil\frac{1}{2}\widetilde{k_{i_{n}}^{n}}\rceil$

members of $K_{n}$ to be covered by $\bigcup_{i\leq k}f_{i}[K_{n}]$.

Fix $i\leqslant k$. By the choice of $n$, either $f_{i}[K_{n}]\subseteq L_{n}$
(if there is $j_{i}$ as above) or $f_{i}[K_{n}]\cap R_{n}\neq\emptyset$ (see
Observation 3.). In the latter case, let $\psi(C_{n}^{j})$ be the member of
the $n$th section which goes onto $R_{n}$ (i.e.,
$f_{i}[\psi[C_{n}^{j}]]\subseteq R_{n}$ – note that $f_{i}[\psi[C_{n}^{j}]]$
cannot intersect both $R_{n}$ and $K_{n}\cup L_{n}$ by (3’)). Suppose that
$j-2\geq 1$. Then $\psi(C_{n}^{j-1})$ either goes onto $R_{n}$ as well or onto
a subset of $\psi(C_{n}^{\widetilde{k^{n}_{i_{n}}}})$ (recall that
$f_{i}[\psi(C_{n}^{j-1})]$ cannot intersect two members of the $n$th section
by condition (3)). As we want to cover $K_{n}$, we can assume that the latter
case holds. By conditions (1) and (4) imposed on $\delta$ and Lemma 3.3,
$\psi(C_{n}^{j-2})$ also goes onto a subset of
$\psi(C_{n}^{\widetilde{k^{n}_{i_{n}}}})$. The same reasoning works for
$\psi(C_{n}^{j+1})$ and $\psi(C_{n}^{j+2})$ instead of $\psi(C_{n}^{j-1})$ and
$\psi(C_{n}^{j-2})$ (whenever $j+2\leq\widetilde{k^{n}_{i_{n}}}$). If we will
carry on this reasoning, we will see that $f_{i}[K_{n}]$ can cover at most a
half of all members of $K_{n}$, however it will be necessary the right-hand
half.

The previous paragraph shows that $\bigcup_{i\leq k}f_{i}[K_{n}]$ can cover at
most a half of all members of $K_{n}$. Thus, by the choice of $n$, $K_{n}$
cannot be covered by $\bigcup_{i\leq k}f_{i}[\varphi(A)]$. This finishes the
entire proof. ∎

We are ready to prove our main result.

######  Theorem 3.5.

The set wIFSd is $G_{\delta\sigma}$-hard in $K([0,1]^{d})$, for every
$d\in\mathbb{N}$.

###### Proof.

There is a continuous function $\varphi\colon\mathcal{P}(\mathbb{N}^{2})\to
K([0,1])$ such that

$\varphi^{-1}[wIFS^{1}]=\mathcal{P}(\mathbb{N}^{2})\setminus\\{A\colon\exists_{n}^{\infty}\>\forall_{m}^{\infty}\>\>(n,m)\in
A\\}$

(by Lemma 3.4).

Define $\hat{\varphi}\colon\mathcal{P}(\mathbb{N}^{2})\to K([0,1]^{d})$ by
$\hat{\varphi}(A)=(\varphi(A),0,\ldots,0)$ for all
$A\in\mathcal{P}(\mathbb{N}^{2})$. It is easy to check that $\hat{\varphi}$ is
continuous. Moreover,

$\hat{\varphi}^{-1}[wIFS^{d}]=\mathcal{P}(\mathbb{N}^{2})\setminus\\{A\colon\exists_{n}^{\infty}\>\forall_{m}^{\infty}\>\>(n,m)\in
A\\}.$

Indeed, $B\in\\{A\colon\exists_{n}^{\infty}\>\forall_{m}^{\infty}\>\>(n,m)\in
A\\}$ implies $\hat{\varphi}(B)\notin wIFS^{d}$, since if
$f:[0,1]^{d}\to[0,1]^{d}$ is a weak contraction then so is
$f\upharpoonright[0,1]\times\\{0\\}^{d-1}$. On the other hand, if
$B\notin\\{A\colon\exists_{n}^{\infty}\>\forall_{m}^{\infty}\>\>(n,m)\in A\\}$
then $\hat{\varphi}(B)$ is in wIFSd, since for each weak contraction
$f:[0,1]\to[0,1]$ the map $g:[0,1]^{d}\to[0,1]^{d}$ given by
$g(x_{1},\ldots,x_{d})=(f(x_{1}),0,\ldots,0)$ is a weak contraction as well.
Thus, by Lemma 3.2 the set wIFSd is $G_{\delta\sigma}$-complete. ∎

Unfortunately, we were not able to solve the following problem.

######  Question 3.6.

Let $d\in\mathbb{N}$. Is the set wIFSd Borel?

## References

  * [1] E. D’Aniello, T. H. Steele,  Attractors for iterated function schemes on $[0,1]^{N}$ are exceptional,  Journal of Mathematical Analysis and Applications, 424: 534-541, 2015.
  * [2] E. D’Aniello, T. H. Steele,  Attractors for iterated function systems,  Journal of Fractal Geometry, 3: 95-117, 2016.
  * [3] E. D’Aniello, T. H. Steele,  Attractors for classes of iterated function systems,  European Journal of Mathematics, 5: 116-137, 2019.
  * [4] M. Edelstein,  On fixed and periodic points under contractive mappings,  Journal of London Mathematical Society s1-37, 1: 74-79, 1962.
  * [5] A.S. Kechris,  Classical Descriptive Set Theory,  Springer, New York 1998.
  * [6] P. Klinga, A. Kwela and M. Staniszewski,  Size of the set of attractors for iterated function systems,  Chaos, Solitons and Fractals, 128: 104—107, 2019.
  * [7] M. Nowak, M. Fernández-Martínez,  Counterexamples for IFS-attractors,  Chaos Solitons & Fractals, 89: 316-321, 2016.
  * [8] S. Solecki,  Analytic ideals,  Bulletin of Symbolic Logic, 3: 339-348, 1996.
  * [9] S. M. Srivastava,  A Course on Borel Sets,  New York, Springer, 1998.
  * [10] L. L. Stachó and L. I. Szabó,  A note on invariant sets of iterated function systems,  Acta Mathematica Hungarica, 119: 159-164, 2008.